SRM473 Div1 Medium(500) RightTriangle

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 );
}