bzoj3202：[Sdoi2013]项链

思路：首先考虑如何求珠子个数，一个珠子由a,b,c三个数组成且属于区间[1,a]，并满足gcd(a,b,c)=1。由于要求本质相同，对于a,b,c这样的一个无序的数列且满足gcd(a,b,c)=1，设其总方案数为t1,那么显然本质相同的重复了6次，即(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)，所以要将t1/=6，但如果存在两个数相同，这样的其实只出现了三次，因此还要加上3*这样的情况（设其为t2）的方案数，同时可能有三个相同，这样的情况只可能是(1,1,1)，只出现了一次，又因为计算两个数相同时已经加了三次，所以要再加两次。

即珠子个数=t1+3*t2+2。t1,t2的求法要用到莫比乌斯反演

这个预处理mu可以sqrt(a)处理，然后考虑如何统计答案，联系bzoj4330爱之项链，那个题因为有特殊的东西使得不需要考虑是否本质不同，但本题是要考虑的，可以利用burnside引理，当旋转i格时，一共有gcd(n,i)个循环，且所有循环都是相邻的，这就相当于只考虑这长为gcd(n,i)的一段的合法的方案数，因为这样的话其余部分均可通过这一段置换得到，且本质相同。那这一段合法方案数有哪些呢，首先不仅相邻的不能相同，首尾也不能相同，因为置换后首就和尾相邻了，那么这不就变成了一个环且相邻颜色不同的总方案数了吗，设长为x的环的答案为f(x)，于是最终答案即sigma(f(gcd(n,i)))。（f(x)=(m-1)^x+(x&1?1-m:m-1),m为颜色种类数，具体证明见http://www.cnblogs.com/DUXT/p/5951747.html

然后具体实现过程注意两个细节，一个vfk加强了数据，n有可能是p的倍数，因此不能直接求逆元，处理方法就是对求分子的过程中都对p^2取模，然后分子除以p，再乘以n/p在模p意义下的逆元即可，蒟蒻并不知道这是为什么。。。。。（当且仅当n是p的倍数是才能这么做）

然后可能出现long long*long long%long long，用一个乘爆的小技巧即可（详见函数mul()）。

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 10001005

int cases,a,tot,p=1000000007;
int prime[maxn],mu[maxn],phi[maxn];
bool bo[maxn];
long long n,mod;

long long mul(long long x,long long y){
	long double t2=(long double)x*y/mod;
	long long t1=x*y,t3=(long long)(t1-(long long)t2*mod)%mod;
	return (t3+mod)%mod;
}

long long power(long long a,long long k){
	if (k==0) return 1;
	if (k==1) return a%mod;
	long long x=power(a,k/2),ans=mul(x,x);
	if (k&1) ans=mul(ans,a);
	return ans;
}

long long fphi(long long x){
	if (x<maxn) return phi[x];
	long long ans=x;
	for (int i=2;1ll*i*i<=x;i++)
		if (x%i==0){
			ans=ans-ans/i;
			while (x%i==0) x/=i;
		}
	if (x!=1) ans=ans-ans/x;
	return ans;
}

long long solve(long long m,long long n){
	return ((power(m-1,n)+(n&1?1ll-m:m-1ll))%mod+mod)%mod;
}

void ex_gcd(long long a,long long b,long long &x,long long &y){
	if (!b){x=1,y=0;return;}else ex_gcd(b,a%b,x,y);
	long long x1=x,y1=y;
	x=y1,y=x1-a/b*y1;
}

long long inv(long long a){
	long long x=0,y=0;ex_gcd(a,p,x,y);return (x%p+p)%p;
}

int main(){
	scanf("%d",&cases);mu[1]=1,phi[1]=1;
	for (int i=2;i<maxn;i++){
		if (!bo[i]) prime[++tot]=i,mu[i]=-1,phi[i]=i-1;
		for (int j=1;j<=tot && i*prime[j]<maxn;j++){
			bo[i*prime[j]]=1;
			if (i%prime[j]==0){
				mu[i*prime[j]]=0;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			mu[i*prime[j]]=-mu[i],phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	for (int i=2;i<maxn;i++) mu[i]+=mu[i-1];
	while (cases--){
		scanf("%lld%d",&n,&a);long long ans2=0,ans3=0;
		if (n%p==0) mod=1ll*p*p;else mod=p;
		for (int i=1,j;i<=a;i=j+1){
			j=a/(a/i);
			ans2=(ans2+mul((mu[j]-mu[i-1]),(1ll*(a/i)*(a/i)%mod)))%mod;
			ans3=(ans3+mul((mu[j]-mu[i-1]),mul(1ll*(a/i)*(a/i)%mod,(a/i)%mod)))%mod;
		}
		long long m=mul((ans3+3*ans2%mod+2)%mod,power(6,1ll*p*(p-1)-1)),ans=0;
		for (int i=1;1ll*i*i<=n;i++)
			if (n%i==0){
				ans=(ans+mul(solve(m,i),fphi(n/i)))%mod;
				if (1ll*i*i!=n) ans=(ans+mul(solve(m,n/i),fphi(i)))%mod;
			}
		if (n%p!=0) ans=mul(ans,power(n,mod-2))%p;
		else ans=ans/p,n=n/p,ans=mul(ans,inv(n))%p;
		printf("%lld\n",ans);
	}
	return 0;
}

　　

UPD:一年以后来复习的时候发现后面这个也会证了。。。。。

首先x/y(mod p)=x(mod yp)/p，当且仅当y|x时成立。

证明:令x/y=kp+m，即x=kyp+mp，然后有x=mp(mod yp)，即x/p=m(mod yp)，m就是x/y(mod p)。

然后此题的y=n，且满足y|x，然后用上面的那个公式就能得出以前的那个结论了。。。。。