poj2154 Polya定理+欧拉函数

/*
Time:2019.12.15
Author: Goven
type：Polya定理+欧拉函数
ref:
[知识点]
Burnside引理 + Polya定理 :
https://blog.csdn.net/WhereIsHeroFrom/article/details/79631703
https://blog.csdn.net/liangzhaoyang1/article/details/72639208
https://blog.csdn.net/qq_33765907/article/details/51307937
欧拉定理：
https://blog.csdn.net/ydd97/article/details/47805419
https://blog.csdn.net/zxwsbg/article/details/81488956
 
[代码]
https://blog.csdn.net/acdreamers/article/details/8656247
https://www.cnblogs.com/AKCqhzdy/p/7598571.html
[总结]
https://blog.csdn.net/My_ACM_Dream/article/details/45312365 
*/
#include<iostream>
#include<cstring> 
#define MAXN 100005
using namespace std;

bool isprime[MAXN];
int prime[MAXN];
int cnt;

void getPrimeTable () {
    cnt = 0;
    memset(isprime, true, sizeof(isprime));
    for (int i = 2; i < MAXN; i++) {
        if (isprime[i]) {
            prime[cnt++] = i;
            for (int j = i + i; j < MAXN; j += i) {
                isprime[j] = false;
            }
        }
    }   
}

int phi (int n, int mod) {//欧拉函数 
    int res = n;
    for (int i = 0; prime[i] * prime[i] <= n && i < cnt;i++) {
        if (n % prime[i] == 0) {
            res -= res / prime[i];
            while (n % prime[i] == 0) n /= prime[i];
        }
    } 
    
    if (n > 1) res -= res / n;
    return res % mod;
}

int quick_mod (int a, int b, int mod) {
    a %= mod;
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1; 
    } 
    return res;
}

int main()
{
    getPrimeTable();
    int t, n, p;
    cin >> t;
    while (t--) {
        cin >> n >> p;
        int res = 0;
        for (int i = 1; i * i <= n; i++) {
            if (i * i == n) {
                res = (res + quick_mod(n, i - 1, p) * phi(i, p)) % p;
            }
            else if (n % i == 0) {
                res = (res + quick_mod(n, i - 1, p) * phi(n / i, p) + quick_mod(n, n / i - 1, p) * phi(i, p)) % p;
            } 
        }
        
        cout << res << endl;
    }
    return 0;
}