首页 > 代码库 > UVa 11440 (欧拉函数) Help Tomisu
UVa 11440 (欧拉函数) Help Tomisu
题意：
给出N和M，统计区间x ∈ [2, N!]，x满足所有素因子都大于M的x的个数。
分析：
首先将问题转化一下，所有素因子都大于M 等价于 这个数与M!互素
对于k大于M!，k与M!互素等价于 k % M! 与 M!互素
所以我们可以求出φ(M!)(φ为欧拉函数) 然后乘以N! / M!，最后答案再减一(因为是从2开始统计的)
欧拉函数的公式为a
phifac[n] = φ(n!)，我们递推求phifac
当n为合数时，n!和(n-1)!的素因数的集合是一样的，所以phifac[n] = n * phifac[n-1]
当n为素数是，n!中多了一个素因子n，公式中也多了一项(1 - 1/n)，所以phifac[n] = n * (n-1) / n * phifac[n-1] = (n-1) * phifac[n-1]
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxn = 10000000 + 10; 5 const int MOD = 100000007; 6 int phifac[maxn]; 7 bool vis[maxn]; 8 9 void sieve(int n)10 {11 int m = sqrt(n + 0.5);12 for(int i = 2; i <= m; ++i) if(!vis[i])13 for(int j = i*i; j <= n; j += i)14 vis[j] = true;15 }16 17 int main()18 {19 sieve(10000000);20 phifac[1] = phifac[2] = 1;21 for(int i = 3; i <= 10000000; ++i)22 phifac[i] = (long long) phifac[i-1] * (vis[i] ? i : i-1) % MOD;23 24 int n, m;25 while(scanf("%d%d", &n, &m) == 2)26 {27 if(n == 0 && m == 0) break;28 int ans = phifac[m];29 for(int i = m+1; i <= n; ++i) ans = (long long)ans * i % MOD;30 printf("%d\n", (ans-1+MOD)%MOD);31 }32 33 return 0;34 }
UVa 11440 (欧拉函数) Help Tomisu
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。