prufer数列+高精度
http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html
详细的介绍可以看这篇blog
知道这个之后 只要计算prufer数列的个数就好了
首先将有度数限制的所有点数一下,这些点的度数-1就是在数列中出现的次数,这可以用含有重复元素的排列来解决。剩下来的位置可以用任意一个没有度数限制的点来填,乘法原理一下即可。
注意特判n=1和2的情况。
计算组合数的时候除法除单精度的数即可
#include <cstdio> #include <algorithm> using namespace std; const int MOD=10,N=5010; struct bigint{int a[N]; void reset(){for(int i=0;i<N;i++) a[i]=0;a[0]=1;} void operator =(int x){ reset(); for(;x;x/=MOD,a[0]++) a[a[0]]=x%MOD; if(a[0]>1) a[0]--; } void print(){ for(int i=a[0];i;i--) putchar(a[i]+'0'); } }ans; int n,s[N],sum,sum2; bigint operator *(bigint x,int y){ for(int i=1;i<=x.a[0];i++) x.a[i]*=y; for(int i=1;i<x.a[0];i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD; for(int& i=x.a[0];x.a[i]>=MOD;i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD; return x; } bigint operator /(bigint x,int y){ bigint z;int tmp=0; z=0;z.a[0]=x.a[0]; for(int i=x.a[0];i;i--) z.a[i]=(tmp*MOD+x.a[i])/y,tmp=(tmp*MOD+x.a[i])%y; for(int &i=z.a[0];!z.a[i] && i;) i--; if(!z.a[0]) z.a[0]++; return z; } int main(){ scanf("%d",&n); if(n==1){ scanf("%d",&s[1]); printf(s[1]?"0":"1"); return 0; } for(int i=1;i<=n;i++) { scanf("%d",&s[i]),s[i]>=1?sum+=s[i]-1:sum2++; if(!s[i]) {printf("0");return 0;} } if(sum>n-2) {printf("0");return 0;} ans=1; for(int i=n-2;i>=n-2-sum+1;i--) ans=ans*i; for(int i=1;i<=n;i++) if(s[i]>1) for(int j=1;j<=s[i]-1;j++) ans=ans/j; for(int i=1;i<=n-2-sum;i++) ans=ans*(sum2); ans.print(); return 0; }
考虑枚举gcd(i,n) =d 那么只要计数有多少个数和N的gcd是d
显然是phi(n/d)个
假设一个数可以表示成$p_{1}^{a1}+p_{2}^{a2}+...$,那么phi的结果就是 $(p_{1}-1)*p_{1}^{a1-1}*(p_{2}-1)*p_{2}^{a2-1}...$每次找到一个约数之后除干净就可以保证每次找到的都是质因数
计算phi是$\sqrt{n}$(枚举约数的复杂度) 枚举公约数$\sqrt{n}$ 时间复杂度$\sqrt{n}$
#include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long LL; LL n,sq,ans; LL phi(LL x){ LL tmp=(LL)sqrt(x),ret=1; for(int i=2;i<=tmp;i++){ if(x%i==0){ ret*=i-1;x/=i; while(x%i==0) x/=i,ret*=i; } } if(x>1)ret=ret*(x-1); return ret; } int main(){ scanf("%lld",&n);sq=(LL)sqrt(n); for(int i=1;i<=sq;i++){ if(n%i==0) { ans+=i*phi(n/i); if(n/i!=i) ans+=(n/i*phi(i)); } } printf("%lld",ans); }
注意一个性质 k%n=k-k/(k/n)
于是可以化简成n*k-(k/i)*i (1<=i<=min(n,k))
只要枚举k/i就可以了,令枚举的这个k/i为t
每一个满足 k/i=t的都在一个区间里
在这里说一下枚举的方法 这个方法复杂度是$\sqrt{n}$
for(int a=1;a<=min(n,k);a= k/(k/a)+1){ //todo 两个a之间就是对应k/i= k/a 的区间 }
代码如下
#include <cstdio> #include <algorithm> using namespace std; typedef long long LL; LL n,k,ans,t; LL min(LL a,LL b){return a<b?a:b;} int main(){ // freopen("1257.in","r",stdin);freopen("1257.out","w",stdout); scanf("%lld%lld",&n,&k); for(t=1;t<=min(n,k);t=k/(k/t)+1){ LL nxt=min(k/(k/t),n); nxt=min(nxt,k); ans+=(k/t)*(t+ nxt )*(nxt-t+1)/2; } ans=n*k-ans; printf("%lld",ans); return 0; } for(int a=1;a<=min(n,k);a= k/(k/a)+1){ //todo }
有一个结论 一个点(x,y)到原点 经过gcd(x,y)个点 自己试一下就知道了
于是这题只要求一下$(\sum_{i=1}^{n-1}phi(i)*2)+1$就好了 n的范围很小没必要用线性筛
#include <cstdio> #include <algorithm> using namespace std; const int N=40010; int p[N],phi[N],n,vis[N],ans; int main(){ scanf("%d",&n); phi[1]=p[1]=1; for(int i=2;i<=n;i++) if(!vis[i]){ p[i]=1; phi[i]=i-1; for(int j=2;j*i<=n;j++){ if(!phi[i*j]) phi[i*j]=i*j; vis[i*j]=1; phi[i*j]=phi[i*j]*(i-1)/i; } } for(int i=1;i<n;i++) ans+=phi[i]*2; printf("%d",ans+1); return 0; }
这题就是求 $\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)*2-1)$
我们考虑枚举k使 gcd(i,j)=k
定义 g[k]表示以k为公约数的i,j有多少对,f[k]表示以k为最大公约数的i,j有多少对
首先我们想k是若干个数的公约数(非最大) 那么 g[k]=(n/k)*(m/k)
而以k为最大公约数的时候 要用g[k]减掉 f[2k],f[3k],f[4k]...于是 $f[k]=g[k]-\sum_{i=1}^{i*k<=min(n,m)}f[i*k]$
最后求一下和就好了
下面是代码
#include <cstdio> #include <algorithm> using namespace std; const int N=100010; typedef long long LL; LL f[N],n,m,mx,ans; int main(){ //freopen("2005.in","r",stdin);freopen("2005.out","w",stdout); scanf("%lld%lld",&n,&m);mx=min(n,m); for(int i=1;i<=mx;i++) f[i]=(n/i)*(m/i); for(int i=mx;i>=1;i--) for(int j=2;j*i<=mx;j++) f[i]-=f[j*i]; for(int i=1;i<=mx;i++) ans+=(i*2-1)*f[i]; printf("%lld",ans); return 0; }