假设现在有两个自然数A和B，S是ABAB的所有约数之和。
请你求出S mod 9901的值是多少。
输入格式
在一行中输入用空格隔开的两个整数A和B。
输出格式
输出一个整数，代表S mod 9901的值。
数据范围
0≤A,B≤5×1070≤A,B≤5×107
输入样例：
2 3
输出样例：
15
注意: A和B不会同时为0。
这种题首先分解质因数，找关系， $A = p_1^{c_1} * p_2^{c_2} * ... * p_n ^ {c_n}$
$A = p_1^{c_1} * p_2^{c_2} * ... * p_n ^ {c_n}$
$A^B = p_1^{B * c_1} * p_2^{B * c_2} * ... * p_n ^ {B * c_n}$
★$A^b$的所有约束可表示为集合{$p_1^{k_1} * p_2^{k_2} * ... * p_n ^ {k_n}$}，其中$(1+p_1+p_1^2+...+p_1^{B*c_1})*(1+p_2+p_2^2+...+p_2^{B*c_2})*...*(1+p_n+p_n^2+...+p_n^{B*c_n})$
★根据乘法分配律，约数之和为 $(1+p_1+p_1^2+...+p_1^{B*c_1})*(1+p_2+p_2^2+...+p_2^{B*c_2})*...*(1+p_n+p_n^2+...+p_n^{B*c_n})$
法一：直接用等差数列的公示求，则要考虑逆元，对于 $(p_i - 1);mod;9901= 0$，则$p_i;mod;9901= 1$，
即 $(1+p_i+p_i^2+...+p_i^{B*c_i}) mod 9901 equiv (1+1+1^2+...+1^{B*c_i}) mod 9901 equiv B*c_i +1 (mod 9901) $
质数[2,71)相乘25位数超过 5e7，也超过了long long，所以a分解质因数不超过19；
代码如下：
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 const int mod = 9901; 6 7 int a, b, m, ans = 1, p[20], c[20]; 8 9 void divide(int n) 10 { 11 m = 0; 12 for (int i = 2; i * i <= n; ++ i) 13 { 14 if (n % i == 0) 15 { 16 p[++ m] = i, c[m] = 0; 17 while (n % i == 0) n /= i, ++ c[m]; 18 } 19 } 20 if (n > 1) p[++ m] = n, c[m] = 1; // n本身就是质数 21 } 22 23 int power(int a, ll b) 24 { 25 int c = 1; 26 for (; b; b >>= 1) 27 { 28 if (b & 1) c = (ll)c * a % mod; 29 a = (ll)a * a % mod; 30 } 31 return c; 32 } 33 34 int main() 35 { 36 scanf("%d%d", &a, &b); 37 if (!b) puts("1"), exit(0); 38 if (!a) puts("0"), exit(0); 39 divide(a); 40 for (int i = 1; i <= m; ++ i) 41 { 42 if ((p[i] - 1) % mod == 0) 43 { 44 ans = ((ll)b * c[i] + 1) % mod * ans % mod; 45 continue; 46 } 47 int x = power(p[i], (long long)b * c[i] + 1); // q^(B * ci) 48 x = (x - 1 + mod) % mod; // q^(B * ci) - 1 49 int y = p[i] - 1; 50 y = power(y, mod - 2); // ÷(q - 1) 求逆元 51 ans = (ll)ans * x % mod * y % mod; 52 } 53 printf("%d", ans); 54 return 0; 55 }
法二：递归求等比数列
sum(p,c) = $(1+p+p^2+...+p^c)$
若c为奇数 sum(p,c) = $(1+p+...+p^{(c-1)/2})+(p^{(c+1)/2}+...+p^c)$
= $(1+p+...+p^{(c-1)/2})+p^{(c+1)/2}*(1+p+...+p^{(c-1)/2})$
= $(1+p^{(c+1)/2})*sum(p,(c-1)/2)$
若c为偶数 sum(p,c) = $(1+p^{c/2})*sum(p,(c-1)/2)$
代码如下
1 #include <cstdio> 2 #define ll long long 3 using namespace std; 4 5 const int mod = 9901; 6 7 int a, b, ans = 1; 8 9 int power(int a, ll b) 10 { 11 int c = 1; 12 for (; b; b >>= 1, a = (ll)a * a % mod) 13 if (b & 1) c = (ll)c * a % mod; 14 return c; 15 } 16 17 int sum(int p, ll c) 18 { 19 if (!c) return 1; 20 if(c & 1) return ((1 + power(p, (c + 1) >> 1)) % mod * sum(p, (c - 1) >> 1)) % mod; 21 return ((1 + power(p, c >> 1)) % mod * sum(p, (c >> 1) - 1) % mod + power(p, c)) % mod; 22 } 23 24 int main() 25 { 26 scanf("%d%d", &a, &b); 27 if (!b) { puts("1"); return 0; } 28 if (!a) { puts("0"); return 0; } 29 for (int i = 2; i <= a; ++ i) 30 { 31 if (a % i) continue; 32 int s = 0; 33 while (!(a % i)) a /= i, ++ s; 34 ans = (ll)ans * sum(i, (ll)s * b) % mod; 35 } 36 printf("%d", ans); 37 return 0; 38 }