BZOJ3202 [Sdoi2013]项链

Problem E: [Sdoi2013]项链

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 427 Solved: 146
[Submit][Status][Discuss]

Description

项链是人体的装饰品之一，是最早出现的首饰。项链除了具有装饰功能之外，有些项链还具有特殊显示作用，如天主教徒的十字架
链和佛教徒的念珠。从古至今人们为了美化人体本身，也美化环境，制造了各种不同风格，不同特点、不同式样的项链，满足了不同肤色、不同民族、不同审美观的人的审美需要。就材料而论，首
饰市场上的项链有黄金、白银、珠宝等几种。珍珠项链为珍珠制成的饰品，即将珍珠钻孔后用线串在一起，佩戴于项间。天然珍珠项链具有一定的护养作用。

最近，铭铭迷恋上了一种项链。与其他珍珠项链基本上相同，不过这种项链的珠子却与众不同，是正三菱柱的泰山石雕刻而成的。三菱柱的侧面是正方形构成的，上面刻有数字。能够让铭铭满意的项链必须满足下面的条件：
1：这串项链由n颗珠子构成的。
2：每一个珠子上面的数字x,必须满足0<x<=a，且珠子上面的数字的最大公约数要恰好为1。两个珠子被认为是相同的，当且仅当他们经过旋转，或者翻转后能够变成一样的。 3：相邻的两个珠子必须不同。
4：两串项链如果能够经过旋转变成一样的，那么这两串项链就是相同的！铭铭很好奇如果给定n和a，能够找到多少不同串项链。由于答案可能很大，所以对输出的答案mod 1000000007。

Input

数据由多组数据构成：
第一行给定一个T<=10，代表由T组数据。
接下来T行，每行两个数n和a。

Output

对于每组数据输出有多少不同的串。

Sample Input

1
2 2

Sample Output

HINT

对于100%的数据：所有的n<=10^14，a<=10^7，T<=10；

题解：JSOI2012 爱之项链升级版，请先做JSOI2012 爱之项链；

　　　推荐博客：http://m.blog.csdn.net/article/details?id=50688526

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int p=1e9+,N=;

 int tot,pri[N],mu[N],phi[N];

 bool vis[N]; ll a;

 ll mod,t1,t3;

 long double t2;

 struct P{

     ll x;

     P(){}

     P(ll _x):x(_x){}

 }n,ans,m,s1,s2,temp,sum[N];

 P operator *(P x,P y){

     ll t1,t3; long double t2;

     t1=x.x*y.x,t2=(long double)x.x*y.x/mod; t3=(ll)(t1-(ll)t2*mod)%mod;

     return (P){(t3+mod)%mod};

 }

 P operator +(P x,P y){return (P)((x.x+y.x)%mod);}

 P operator -(P x,P y){return (P)(((x.x-y.x)%mod+mod)%mod);}

 ll read()

 {

     ll x=,f=; char ch;

     while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;

     while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');

     return x*f;

 }

 /*P ksm(P x,ll k,ll mod)

 {

     P res; res.x=1; for (ll i=k; i; i>>=1,x=x*x) if (i&1) res=res*x;

     return res;

 }*/

 P ksm(P x,ll y,ll p){

     if (y==) return (P)();

     if (y==) return (P)(x.x%p);

     P d=ksm(x,y/,p);

     if (y&) return d*d*x;

     else return d*d;

 }

 ll phii(ll x){

     if (x<N) return phi[x];

     ll t=x;

     for (int i=;i<=sqrt(x);i++){

         if (x%i==){

             t=t-t/i;

             while (x%i==) x/=i;

         }

     }

     if (x>) t=t-t/x;

     return t;

 }

 P work(ll x)

 {

     P res; res.x=;

     res=ksm((P)(m.x-),x,mod);

     if (x&) res=res+(P)(-m.x); else res=res+(P)(m.x-);

     res.x=(res.x+mod)%mod;

     res=res*(P)(phii(n.x/x));

     return res;

 }

 void prepare()

 {

     tot=; memset(vis,,sizeof(vis)); mu[]=phi[]=;

     for (int i=;i<N;i++){

         if (!vis[i]){

             mu[i]=-,phi[i]=i-;

             pri[++tot]=i;

         }

         for (int j=;j<=tot;j++){

             if (1LL*i*pri[j]>=N) break;

             vis[i*pri[j]]=;

             if (i%pri[j]==){

                 mu[i*pri[j]]=,phi[i*pri[j]]=phi[i]*pri[j];

                 break;

             }else mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];

         }

     }

     for (int i=;i<N;i++) sum[i].x=;

     for (int i=;i<N;i++) sum[i].x=sum[i-].x+mu[i];

 }

 int main()

 {

     prepare();

     int T=read();

     while (T--)

     {

         n.x=read(); a=read(); ans.x=; ans.x=m.x=s1.x=s2.x=;

         if (n.x%p==) mod=1ll*p*p; else mod=p;

         for (int j,i=;i<=a;i=j+){

             j=a/(a/i);

             s1=s1+(P)(a/i)*(P)(a/i)*(P)(a/i)*(P)(sum[j]-sum[i-]);

             s2=s2+(P)(a/i)*(P)(a/i)*(P)(sum[j]-sum[i-]);

         }

         m=(P)(s1+s2*(P)((ll))+(P)((ll)))*ksm((P)(),1ll*p*(p-)-,mod);

         for (int i=; 1ll*i*i<=n.x; i++)

         {

             if (n.x%i==){

                 ans=ans+work(i);

                 if (1ll*i*i!=n.x) ans=ans+work(n.x/i);

             }

         }

         mod=p;

         if (n.x%p==)

         {

             ans.x/=p; temp=(P)(n.x/p); temp=ksm(temp,p-,p);

             ans=ans*temp; printf("%lld\n",ans.x%p);

         }

         else

         {

             temp=(P)(n.x); temp=ksm(temp,p-,p);

             ans=ans*temp; printf("%lld\n",ans.x%p);

         }

     }

     return ;

 }

巴特西