intphi(int n){ int ret = n; rep(i, 0, sz(primes)) if (primes[i] <= n) { constint &p = primes[i]; if (n % p == 0) { ret -= ret / p; while (n % p == 0) n /= p; } } else break; if (n > 1) ret -= ret / n; return ret; }
intmain(){ init();
int cases; scanf("%d", &cases); rep(casei, 0, cases) { int ans = 0; scanf("%d%d", &n, &p); for (int d = 1; d * d <= n; ++d) { if (n % d) continue; ans += 1ll * kpow(n, d - 1, p) * phi(n / d) % p; if (d * d != n) ans += 1ll * kpow(n, n / d - 1, p) * phi(d) % p; ans %= p; } printf("%d\n", ans);
constint P = 9973; constint M = 10; constint N = 31625; int n, m, k; vector<int> prime; bool isprime[N];
structMatrix { int a[M][M]; voidinit(int x){ rep(i, 0, m) rep(j, 0, m) a[i][j] = i == j ? x : 0; } voidfill(int x){ rep(i, 0, m) rep(j, 0, m) a[i][j] = x; } inttrace(){ int ret = 0; rep(i, 0, m) ret += a[i][i]; return ret % P; } Matrix operator*(const Matrix &mat) const { Matrix r; r.init(0); rep(i, 0, m) rep(j, 0, m) { rep(k, 0, m) r.a[i][j] += a[i][k] * mat.a[k][j]; r.a[i][j] %= P; } return r; } Matrix operator^(int n) { Matrix r, a = *this; r.init(1); while (n > 0) { if (n & 1) r = r * a; a = a * a, n >>= 1; } return r; } };
inlinevoidinc(int &x, int y){ if ((x += y) >= P) x -= P; }
voidinitPrime(){ memset(isprime, 1, sizeof(isprime)); isprime[0] = isprime[1] = false; rep(i, 2, N) { if (isprime[i]) prime.push_back(i); for (int j = 0; i * prime[j] < N; ++j) { isprime[i * prime[j]] = false; if (i % prime[j] == 0) break; } } }
intphi(int n){ int ret = n; rep(i, 0, sz(prime)) { if (n < prime[i]) break; if (n % prime[i] == 0) { ret -= ret / prime[i]; while (n % prime[i] == 0) n /= prime[i]; } } if (n > 1) ret -= ret / n; return ret; }
intf(int n, int d, Matrix &a){ int fd = (a ^ d).trace(); return phi(n / d) % P * fd % P; }
voidexgcd(int a, int b, int &x, int &y){ if (!b) x = 1, y = 0; else { exgcd(b, a % b, y, x); y -= a / b * x; } }
intinv(int n){ int x, y; exgcd(n, P, x, y); x = (x % P + P) % P; return x; }
intmain(){ initPrime();
int cases; scanf("%d", &cases); while (cases-- > 0) { scanf("%d%d%d", &n, &m, &k); Matrix a; a.fill(1); rep(_k, 0, k) { int x, y; scanf("%d%d", &x, &y); --x, --y; a.a[x][y] = a.a[y][x] = 0; } int ans = 0; for (int d = 1; d * d <= n; ++d) { if (n % d) continue; inc(ans, f(n, d, a)); if (d * d != n) inc(ans, f(n, n / d, a)); } ans = ans * inv(n) % P; printf("%d\n", ans); } return0; }
constint P = 1e9 + 7; constint M = 2; constint N = 31625;
int n, k; vector<int> prime; bool isprime[N];
inlinevoidinc(int &x, int y){ if ((x += y) >= P) x -= P; }
intkpow(int a, int b){ a %= P; int r = 1; while (b > 0) { if (b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P, b >>= 1; } return r; }
structMatrix { int a[M][M]; voidinit(int x){ rep(i, 0, M) rep(j, 0, M) a[i][j] = i == j ? x : 0; } Matrix operator*(const Matrix &mat) const { Matrix r; r.init(0); rep(i, 0, M) rep(j, 0, M) rep(k, 0, M) inc(r.a[i][j], 1ll * a[i][k] * mat.a[k][j] % P); return r; } Matrix operator^(int n) { Matrix r, a = *this; r.init(1); while (n > 0) { if (n & 1) r = r * a; a = a * a, n >>= 1; } return r; } };
voidinitPrime(){ memset(isprime, true, sizeof(isprime)); isprime[0] = isprime[1] = false; rep(i, 2, N) { if (isprime[i]) prime.push_back(i); for (int j = 0; i * prime[j] < N; ++j) { isprime[i * prime[j]] = false; if (i % prime[j] == 0) break; } } }
intphi(int n){ int ret = n; rep(i, 0, sz(prime)) { if (n < prime[i]) break; if (n % prime[i] == 0) { ret -= ret / prime[i]; while (n % prime[i] == 0) n /= prime[i]; } } if (n > 1) ret -= ret / n; return ret; }
intf(int n, int m, int d, Matrix &a){ int fd = 1ll * m * (a ^ d).a[0][0] % P; return1ll * fd * phi(n / d) % P; }
intmain(){ initPrime(); while (~scanf("%d%d", &n, &k)) { int ans = 0; int m = k - 1; // #color for small beads Matrix a; a.a[0][0] = 0, a.a[0][1] = m - 1; a.a[1][0] = 1, a.a[1][1] = m - 2; for (int d = 1; d * d <= n; ++d) { if (n % d) continue; inc(ans, f(n, m, d, a)); if (d * d != n) inc(ans, f(n, m, n / d, a)); } ans = 1ll * ans * kpow(n, P - 2) % P; ans = 1ll * ans * k % P; printf("%d\n", ans); } return0; }