等比数列求和 （快速幂 + 逆元） |
您所在的位置：网站首页 › 数列求和求法 › 等比数列求和 （快速幂 + 逆元） |
|
求一个等比数例之和， 并让他对一个数取模。 用到等比数列求和公式， 快速幂， 逆元。 不会证明， 下面给出代码。 #include #include #include typedef long long ll; ll multi(ll a,ll b,ll m) // 二分乘法 { ll ans = 0; a %= m; while(b) { if(b & 1) { ans = (ans + a) % m; b--; } b >>= 1; a = (a + a) % m; } return ans; } ll quick_mod(ll a,ll b,ll mod) { ll res = 1; while(b) { if(b % 2 == 1) res = multi(res, a, mod); // 二分乘法 不然会数据溢出 b >>= 1; a = multi(a, a, mod); // 二分乘法 不然会数据溢出 } return res; } int main() { ll a, b, mod=9901; scanf("%I64d %I64d",&a, &b); // 首项为 1 ， 公比为 a，长度 为 b 的等比数例求和 printf("%I64d\n",((quick_mod(a,b,mod*(a-1)) - 1) / (a-1))); return 0; }Sumdiv
Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 23623 Accepted: 5876 Description Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901). Input The only line contains the two natural numbers A and B, (0 = 1; a = multi(a, a, mod); } return res; } int main() { ll a, b, mod=9901; scanf("%I64d %I64d",&a, &b); if(a == 1) { printf("1\n"); return 0; } prime(); ll ans = 1; int num = 0; for(int i=1; p[i]*p[i] 1) printf("%I64d\n",ans * ((quick_mod(a, b+1, m) + m - 1) / (a-1)) % mod); else printf("%I64d\n",ans % mod); return 0; }
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |