弹药科技解题报告

弹药科技解题报告

题目模型：

假设G(d)表示d的因子个数。已知 F(N) = N - phi(N) - G(N) + 1。

求解 F(N!)MOD1000000007 。 N<= 1000000

原题并不是这样给出的，但是笔者只推到了这个公式，向下就不会做了，所以解题报告就从这里写起。如果真的像上面一样，求F(N)的话，笔者还是有思路的，先求欧拉，再求因子数，再计算，但是这里实在是太。。。居然是N的阶乘，要知道，光20！= 2432902008176640000 了，再来个一百万的阶乘，回家看孩子吧。。

所以，这个题目要这样建立思路:

首先，大数据求Mod,一般都要涉及到每步取模，这是一定的，

其次，要知道要求什么东西，这里涉及阶乘，欧拉函数和约数个数，所以要想到这几想东西：阶乘，欧拉phi的求法，约数个数定理，

再向下就要想到这些东西的性质是什么。

阶乘没什么好说的，for(i <- 1 to n) fac *= i mod 1000000007;

重点是要说一下欧拉函数和约数个数定理，首先贴下约数个数定理：

这东西自己百度一下就可以。至于怎么求一个数的约数个数自行百度，其实是笔者比较懒。

然后要贴一个十分重要的欧拉函数的性质：

若a是N的质因子，如果(N%a == 0 && (N/a)%a == 0) ,则Euler(N) = Euler(N/a)*a;如果(N%a == 0 && (N/a)%a != 0) 则Euler(N) = Euler(N/a) *(a-1)。有了这个神奇的分式，那么就可以在O(N)的时间内求出N! 的phi了。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <iostream>
 6  
 7 using namespace std;
 8 const int lala = 1000000007;
 9 int N;
10  
11 long long fac = 1;
12 int Ans = 0;
13 int upper = 0,divisor_cnt = 1,euler_phi = 1;
14 bool vi[1011001];
15 int prime[1110001];
16 int c[805005];
17  
18 int main(){
19     cin >> N;
20      
21     for(int i = 2;i <= N;++ i){
22         if(!vi[i]){
23             ++ upper;
24             prime[upper] = i;   
25             for(int j = 2*i;j <= N;j += i)
26                 vi[j] = true;
27         }
28     }   
29     for(int i = 2;i <= N;++ i)
30         fac =(long long) (fac*i) % lala;
31      
32     long long now_pri;
33     for(int i = 1;i <= upper;++ i){
34         now_pri = prime[i];
35         while(now_pri <= N){
36             c[i] += N/now_pri;
37             now_pri = (long long)now_pri * prime[i];
38         }
39     }   
40     for(int i = 1;i <= upper;++ i)
41         divisor_cnt = divisor_cnt *(long long)(c[i]+1) % lala;
42      
43     for(int i = 2;i <= N;++ i)
44         if(!vi[i])
45             euler_phi = euler_phi*(long long)(i-1) % lala;
46         else
47             euler_phi = euler_phi*(long long)i % lala;
48              
49     Ans = fac - euler_phi - divisor_cnt + 1;
50     while(Ans < 0)
51         Ans += lala;
52          
53     cout << Ans;
54     return 0;
55 }

View Code

弹药科技 解题报告

弹药科技解题报告