[CodeVS 月赛 #7 day1] FFF 团卧底的算式

发表于   |  

主要是有个gcd(i,n)的公式，所以我重发一下。

内存限制: 128.0MB 时间限制: 1s 测试数据: 10 * 10pts

题目描述 Description

你在某日收到了 FFF 团卧底的求助，他的妹子向他询问了一道算式，而他并不会做，于是这个问题就交给你了：

其中$f(i)$为小于等于$i$且与$i$互素的元素的个数。

输入描述 Input Description

第一行为 $n$

输出描述 Output Description

一行，为运算后的答案

样例输入 Sample Input

6

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

样例解释： $(1+1)+(1+2+3+2+1+6) mod 6=2+3=5$
数据范围：对于100%的数据 $n<=10^{14}$

Solution

对于每个sigma，逐个击破

第一个sigma，我猜gcd（n+i，n*i）都等于1，跑了个程序测了一下发现就是这么回事，然后就解决了。

第二个sigma比较坑爹，有一个叫做Pillai函数的东西。

设函数g(n) = gcd(i,n) (1<=i<=n)，对于任意给定的i 。 g(1) = 1 ,g(n)=g(m1)*g(m2) (n=m1*m2 且 （m1, m2）= 1)，由积性函数定义,g是积性函数。由具体数学上的结论，积性函数的和也是积性的。所以f(n) = ∑gcd(i, n)也是积性函数。n>1时n可以被唯一分解 n=p1^a1*p2^a2*…*ps^as，由于f(n)是积所以f(n) = f(p1^a1)*f(p2^a2)*…f(pr^ar)。所以只要求f(pi^ai)就好，如果d是n的一个约数，那么1<=i<=n中gcd(i,n) = d的个数是phi(n/d)，即n/d的欧拉函数

1
2
3
f(pi^ai) =  Φ（pi^ai）+pi*Φ（pi^(ai-1)）+pi^2*Φ（pi^(ai-2)）+...+pi^(ai-1)* Φ（pi）+ pi^ai *Φ（1）
= pi^(ai-1)*(pi-1) + pi*pi^(ai-2)*(pi-1)....+pi^ai
=  pi^ai*(1+ai*(1-1/pi))

接下来把各个项乘起来OK

第三个乱搞即可。。

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <iostream>
#define LL long long
#define maxm 100000
using namespace std;
LL n;
LL prime[maxm],u[maxm],phin,phi[maxm][1000];
int cnt=0;
void get_prime(){
    LL m=n;
    for (LL i=2;i*i<=n;i++){
        if (m % i==0){
            prime[++cnt]=i;
            while (m % i ==0) {
                m/=i;
                u[cnt]++;
            }
        }
    }
    if (m>1) {
        prime[++cnt]=m;
        u[cnt]=1;
    }
}
void get_phi(){
    LL m=n;
    for (int i=1;i<=cnt;i++){
        m /= prime[i];
        m *= prime[i]-1;
    }
    phin = m;
    for (int i=1;i<=cnt;i++){
        phi[i][1]=prime[i]-1;
        for (int j=2;j<=u[i];j++){
            phi[i][j]=phi[i][j-1]*prime[i];
        }
    }
}
LL sig2;
LL pow(LL a,LL b){
    LL ret=1;
    while (b){
        if ((b&1)==1) ret=ret*a;
        a*=a;
        b>>=1;
    }
    return ret;
}
void get_sig2(){
    LL ret=1;
    for (int i=1;i<=cnt;i++){
        LL x=pow(prime[i],u[i]-1)*(prime[i]+u[i]*(prime[i]-1));
        ret=ret*x;
    }
    sig2=ret;
}
LL ret=1,sig3=0;
void get_sig3(int i){
    if (i>cnt){
        sig3+=ret;
        return;
    }

    for (int j=1;j<=u[i];j++){
        ret*=phi[i][j]; 
        get_sig3(i+1);
        ret/=phi[i][j]; 
    }

    get_sig3(i+1);

}
int main(){

    cin>>n;
    get_prime();    
    get_phi();
    get_sig2();
    get_sig3(1);
    LL ans=phin+sig2 % sig3;
    cout<<ans<<endl;
    return 0;
}