Codeforces Round #280 (Div. 2), problem: (E) Vanya and Field

還是寫的有點慢

#include<cstdio>
#include<cstdlib>
typedef long long int int64;
int arr[1000000] = {0};
bool seive[1000001] = {0};
int64 phi[1000001];
int64 _pow(int64 a, int n, int64 m){
    a%=m;
    if(n == 0) return 1;
    if(n == 1) return a;
    int64 half = _pow(a, n/2, m);
    half = (half*half)%m;
    if(n&1) return (half*a)%m;
    return half;
}
int main()
{
    for(int lx = 1;lx <= 1000000;lx++)
        phi[lx] = lx;
    for(int lx = 2;lx <= 1000000;lx++)
        if(seive[lx] == 0)
            for(int ly = 1;ly*lx <= 1000000;ly++)
                seive[ly*lx] = 1, phi[ly*lx] = phi[ly*lx]/lx*(lx-1);
    int64 n, m, dx, dy;;
    scanf("%I64d %I64d %I64d %I64d", &n, &m, &dx, &dy);
    for(int lx = 0;lx < m;lx++){
        int64 a, b;scanf("%I64d %I64d", &a, &b);
        int64 nn = (b*_pow(dy, phi[n]-1, n))%n;
        int64 p = ((a - dx*nn)%n + n)%n;
//        printf("step = %I64d, add on %I64d\n", nn, p);
        arr[p]++;
    }
    int maxpos = 0;
    for(int lx = 1;lx < n;lx++)
        if(arr[lx] > arr[maxpos])
            maxpos = lx;
    printf("%d 0\n", maxpos);
//    while(1);
    return 0;
}