BZOJ 2705 Longge的问题

发表于 | 更新于

Link

Solution

考虑NN的一个约数dd会对答案产生多大的贡献，即有多少i≤N,gcd(i,N)==di\le N,gcd(i,N)==d 稍加分析就知道是ϕ(Nd)\phi(\dfrac Nd)个。 ii从11枚举到N\sqrt N，如果是约数就O(N)O(\sqrt N)地计算ϕ(i)\phi(i)和ϕ(Ni)\phi(\dfrac Ni)。

这样不会T。。从11到NN的约数个数和是∑[Ni]\sum [\dfrac Ni]，所以NN的约数个数就是∑[Ni]−∑[N−1i]\sum[\dfrac Ni]-\sum[\dfrac {N-1}i]，取值不会很大的。。 求靠谱一些的靠谱性证明。。。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define llred(x) scanf("%lld",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
const int N=65537,MAXN=N+10;
int phi[MAXN],prime[MAXN],pcnt;
void Prep()
{
	phi[1]=1;
	static bool notp[MAXN];
	for(int i=2;i<=N;i++)
	{
		if(!notp[i])
		{
			prime[++pcnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=pcnt && i*prime[j]<=N;j++)//保证prime[j]是最小的质因子
		{
			notp[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else
				phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
}
LL Phi(LL x)
{
	if(x<=N) return phi[x];
	LL mid=(LL)sqrt(x+0.5);
	LL res=x;
	for(int i=1;i<=pcnt && prime[i]<=x;i++) 
		if(x%prime[i]==0)
		{
			res=res*(prime[i]-1)/prime[i];
			while(x%prime[i]==0) x/=prime[i];
		}
	if(x>1) res=res*(x-1)/x;
	return res;
}
int main()
{
	//freopen("input","r",stdin);
	Prep();
	LL n;llred(n);
	LL ANS=0,mid=(LL)sqrt(n+0.5);
	for(int i=1;i<=mid;i++)
		if(n%i==0)
			ANS+=Phi(n/i)*i,ANS+=Phi(i)*(n/i);
	printf("%lld\n",ANS);
	return 0;
}