Submission #1112534

---

Source Code Expand

#include <iostream>

int pow_mod(int x, int n, int mod) {
    int ans = 1;
    
    while(n != 0) {
        if(n & 1)
            ans = (ans * x) % mod;
        
        x = (x*x) % mod;
        n >>= 1;
    }
    
    return ans;
}

int count[10010];

int main() {
    int p, n;
    
    std::cin >> p >> n;
    
    for(int i = 0; i < p; ++i) {
        ++count[pow_mod(i, n, p)];
    }
    
    int zero = 0;
    int cnt = 0;
    for(int i = 0; i < p; ++i) {
        zero += count[0] * count[i] * count[(p - i) % p];
        
        if(i > 0 && count[i] > 0)
            ++cnt;
    }
    
    int one = 0;
    for(int i = 0; i < p; ++i) { // x
        one += count[1] * count[i] * count[(p + 1 - i) % p];
    }
    
    std::cout << zero + one * cnt << std::endl;
}

Submission Info

Judge Result