本文共 1399 字，大约阅读时间需要 4 分钟。
题意：求a^b的所有约数和对1e9+7取模的结果
思路：对于一个数p,进行唯一分解，则p=P1^M1*P2^M2*...*Pn^Mn，则p的所有约数之和等于（P1^0+P1^1+...+P1^M1）*（P2^0+P2^1+...+P2^M2）*...*（Pn^0+Pn^1+...+Pn^Mn），
p^t=P1^(M1*t)*P2^(M2*t)*...*Pn^(Mn*t)，每一个（Pn^0+Pn^1+...+Pn^Mn）利用等比数列可以直接推出公式为（Pn^(Mn*t+1)-1）/（Pn-1），用快速幂和乘法逆元即可。
注意:n的唯一分解只需要试遍sqrt(n)的所有质数即可，若最后n除不尽，那么最后的n一定是质数。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #define x first 17 #define y second 18 #define pb push_back 19 #define mp make_pair 20 #define lson l,m,rt*2 21 #define rson m+1,r,rt*2+1 22 #define mt(A,B) memset(A,B,sizeof(A)) 23 using namespace std; 24 typedef long long LL; 25 const double PI = acos(-1); 26 const int N=1e5+10; 27 const LL mod=1e9+7; 28 const int inf = 0x3f3f3f3f; 29 const LL INF=0x3f3f3f3f3f3f3f3fLL; 30 vector prime; 31 int vis[N]; 32 void init() 33 { 34 mt(vis,0); 35 LL m=sqrt(N+0.5); 36 for(LL i=2;i<=m;i++) 37 { 38 if(!vis[i])for(LL j=i*i;j<=N;j+=i)vis[j]++; 39 } 40 for(LL i=2;i >T; 82 for(int d=1;d<=T;d++) 83 { 84 cout<<"Case "< <<":"<<" "; 85 ans=1; 86 cin>>n>>m; 87 for(int i=0;i 1)ans=(ans*solve(n,(LL)(m+1)))%mod;102 cout< <
转载于:https://www.cnblogs.com/27sx/p/6417897.html
