首页 > 代码库 > Light OJ 1054 Efficient Pseudo Code 求n^m的约数和
Light OJ 1054 Efficient Pseudo Code 求n^m的约数和
题目来源:Light OJ 1054 Efficient Pseudo Code
题意:求n的m次这个数的所有的约数和
思路:首先对于一个数n = p1^a1*p2^a2*p3^a3*…*pk^ak 约束和s = (p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak)
然后就是先求素数表 分解因子 然后求p1^0+p1^1+p1^2+…p1^a1 这是一个以1开始的等比数列 就是(1-q^n)/(1-q) 最高次用快速幂求 此外有除法 除以(1-q)乘以(1-q)的逆元
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long LL; const long long mod = 1000000007; const int maxn = 1000010; //筛素数 int vis[maxn]; LL prime[maxn]; LL pow_mod(LL a, LL p) { LL ans = 1; while(p) { if(p&1) { ans *= a; ans %= mod; } a *= a; a %= mod; p >>= 1; } return ans; } void sieve(int n) { int m = sqrt(n+0.5); memset(vis, 0, sizeof(vis)); vis[0] = vis[1] = 1; for(int i = 2; i <= m; i++) if(!vis[i]) for(int j = i*i; j <= n; j += i) vis[j] = 1; } int get_primes(int n) { sieve(n); int c = 0; for(int i = 2; i <= n; i++) if(!vis[i]) prime[c++] = i; return c; } int main() { int c = get_primes(100000); int cas = 1; int T; scanf("%d", &T); while(T--) { LL n, m, ans = 1; scanf("%lld %lld", &n, &m); for(int i = 0; i < c && prime[i]*prime[i] <= n; i++) { if(n%prime[i] == 0) { int sum = 0; while(n%prime[i] == 0) { sum++; n /= prime[i]; } ans *= pow_mod(prime[i], sum*m+1)-1; ans %= mod; ans *= pow_mod(prime[i]-1, mod-2); ans %= mod; //ans = (ans+mod)%mod; } } if(n > 1) { ans *= pow_mod(n%mod, m+1)-1; ans %= mod; ans *= pow_mod((n-1)%mod, mod-2); ans %= mod; ans = (ans+mod)%mod;//此句不加会错 原因不明 求告知 } printf("Case %d: %lld\n", cas++, ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。