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开始统计的)

欧拉函数的公式为 $UVa 11440 (欧拉函数) Help Tomisu$ 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]

 #include <cstdio>

 #include <cmath>

 const int maxn =  + ;

 const int MOD = ;

 int phifac[maxn];

 bool vis[maxn];

 void sieve(int n)

 {

     int m = sqrt(n + 0.5);

     for(int i = ; i <= m; ++i) if(!vis[i])

         for(int j = i*i; j <= n; j += i)

             vis[j] = true;

 }

 int main()

 {

     sieve();

     phifac[] = phifac[] = ;

     for(int i = ; i <= ; ++i)

         phifac[i] = (long long) phifac[i-] * (vis[i] ? i : i-) % MOD;

     int n, m;

     while(scanf("%d%d", &n, &m) == )

     {

         if(n ==  && m == ) break;

         int ans = phifac[m];

         for(int i = m+; i <= n; ++i) ans = (long long)ans * i % MOD;

         printf("%d\n", (ans-+MOD)%MOD);

     }

     return ;

 }

代码君

秒客网

UVa 11440 (欧拉函数) Help Tomisu

相关文章