SRM473 Div1 Medium(500) RightTriangle
赤点を描く場所は描く順番に依存しないので、先に各場所が何回選ばれるかを求め、重複の処理は後でまとめて行う。
直角三角形の斜辺は外接円の直径となるので、向かい合っていて両方に赤点が描かれている場所を数える。
#include <vector> using namespace std; class RightTriangle { public: long long triangleCount( int places, int points, int a, int b, int c ); }; long long RightTriangle::triangleCount( int places, int points, int a, int b, int c ) { if ( places % 2 == 1 ) return 0; vector<int> red( places ); for ( long long n=0; (int)n<points; n++ ) red[ (int)( ( a*n%places*n + b*n + c ) % places ) ]++; int ex = 0; for ( int i=0; i<2; i++ ) for ( int j=0; j<places; j++ ) { if ( red[j] >= 2 ) ex += red[j] - 1, red[j] = 1; if ( red[j] == 0 && ex > 0 ) ex--, red[j] = 1; } int num = 0; for ( int i=0; i<places/2; i++ ) if ( red[i] && red[i+places/2] ) num++; return (long long)num * ( points - 2 ); }