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
2 2
Sample Output
HINT
对于100%的数据:所有的n<=10^14,a<=10^7,T<=10;
#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 ;
}