Description

牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 k

进制下，一个数的小数部分是纯循环的，那么它就是美的。现在，牛牛想知道：对于已知的十进制数 n 和 m，在

kk 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 xy 表示,其中 1≤x≤n,1≤y≤m，且 x,y是整数

。一个数是纯循环的，当且仅当其可以写成以下形式：a.c1˙c2c3…cp-1cp˙其中，a 是一个整数，p≥1；对于 1

≤i≤p，ci是 kk 进制下的一位数字。例如，在十进制下，0.45454545……=0.4˙5˙是纯循环的，它可以用 5/11

、10/22 等分数表示；在十进制下，0.1666666……=0.16˙则不是纯循环的，它可以用 1/6 等分数表示。需要特

别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 0 的循环或是 k?1 的循环；而一个小

数部分非 0 的有限小数不是纯循环的。

Input

只有一行，包含三个十进制数N,M,K意义如题所述,保证 1≤n≤10^9,1≤m≤10^9,2≤k≤2000

Output

一行一个整数，表示满足条件的美的数的个数。

Sample Input

2 6 10

Sample Output

4
explanation
满足条件的数分别是：
1/1=1.0000……
1/3=0.3333……
2/1=2.0000……
2/3=0.6666……
1/1 和 2/2 虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，1/3 和 2/6 也只计数一次。

解题思路：

一个喜闻乐见的性质，只要x/y中y与k互质就好了。

所以这道题就是：

$\sum_{i=1}^{N}\sum_{j=1}^{M}\epsilon(gcd(i,j))\epsilon (gcd(j, k))$

$\sum_{j=1}^{M}\epsilon(gcd(j,k))\sum_{i=1}^{N}\epsilon(gcd(i,j))$

$\sum_{j=1}^{M}\epsilon(gcd(j,k))\sum_{i=1}^{N}\sum_{d|gcd(i,j)}\mu(d)$

$\sum_{j=1}^{M}\epsilon(gcd(j,k))\sum_{d=1}^{min(N,M)}\mu(d)\sum_{d|i}^{N}1$

$\sum_{j=1}^{M}\epsilon(gcd(j,k))\sum_{d=1}^{min(N,M)}\mu(d)\left \lfloor \frac{N}{d} \right \rfloor$

${\sum_{d=1}^{min(N,M)}\epsilon(gcd(d,k))\mu(d)\left \lfloor \frac{N}{d} \right \rfloor} \sum_{i=1}^{\left \lfloor \frac{M}{d} \right \rfloor}\epsilon(gcd(i,k))$

莫比乌斯到这里结束，现在你可以获得84分，接下来是真正的烧脑环节。

我讲的不好，可以看这位巨佬的

总之，将后面那个预处理出来。

再二元递归求解整体。

代码：

 #include<map>

 #include<cstdio>

 #include<algorithm>

 typedef long long lnt;

 const int N=;

 struct pos{lnt x,k;pos(lnt a,lnt b){x=a,k=b;}};

 bool operator < (pos a,pos b){if(a.x!=b.x)return a.x<b.x;return a.k<b.k;}

 struct Dark_map{

     std::map<pos,lnt>A;

     void insert(lnt x,lnt k,lnt v){A[pos(x,k)]=v;return ;}

     bool hav(lnt x,lnt k){return A.find(pos(x,k))!=A.end();}

     lnt val(lnt x,lnt k){return A[pos(x,k)];}

 }S;

 struct New_map{

     std::map<lnt,lnt>A;

     lnt a[N];

     void insert(lnt p,lnt x){if(p<N)a[p]=x;else A[p]=x;return ;}

     bool hav(lnt x){if(x<N)return true;return A.find(x)!=A.end();}

     lnt val(lnt x){if(x<N)return a[x];return A[x];}

 }Miu;

 int prime[N];

 int miu[N];

 bool vis[N];

 int cnt;

 int n,m,k;

 int twd[N];

 int lst[N];

 lnt f[];

 int hd[];

 lnt gcd(lnt a,lnt b){if(!b)return a;return gcd(b,a%b);}

 void adde(int f,int t){cnt++;twd[cnt]=t;lst[cnt]=hd[f];hd[f]=cnt;return ;}

 void gtp(void)

 {

     for(int i=;i<=k;i++)f[i]=f[i-]+(gcd(i,k)==);

     for(int i=;i<=k;i++)for(int j=i;j<=k;j+=i)adde(j,i);

     miu[]=,cnt=;

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

     {

         if(!vis[i])

         {

             prime[++cnt]=i;

             miu[i]=-;

         }

         for(int j=;j<=cnt&&i*prime[j]<N;j++)

         {

             vis[i*prime[j]]=true;

             if(i%prime[j]==)

             {

                 miu[i*prime[j]]=;

                 break;

             }

             miu[i*prime[j]]=-miu[i];

         }

     }

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

         Miu.insert(i,Miu.val(i-)+1ll*miu[i]);

     return ;

 }

 lnt F(lnt x)

 {

     return (x/k)*f[k]+f[x%k];

 }

 lnt MIU(lnt x)

 {

     if(Miu.hav(x))

         return Miu.val(x);

     lnt tmp=;

     for(int i=,j;i<=x;i=j+)

     {

         j=x/(x/i);

         tmp+=1ll*(j-i+)*MIU(x/i);

     }

     tmp=-tmp;

     Miu.insert(x,tmp);

     return tmp;

 }

 lnt SUM(lnt Nn,lnt Kk)

 {

     if(S.hav(Nn,Kk))

         return S.val(Nn,Kk);

     lnt tmp=;

     if(Nn<);

     else if(Kk==)

         tmp=MIU(Nn);

     else{

         for(int I=hd[Kk];I;I=lst[I])

         {

             int x=twd[I];

             lnt TMP=miu[x];

             if(!TMP)

                 continue;

             tmp+=SUM(Nn/x,x);

         }

     }

     S.insert(Nn,Kk,tmp);

     return tmp;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&k);

     gtp();

     lnt ans=;

     for(int i=,j;i<=n&&i<=m;i=j+)

     {

         j=std::min(n/(n/i),m/(m/i));

         ans+=(SUM(j,k)-SUM(i-,k))*(lnt)(n/i)*F(m/i);

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

BZOJ4652: [Noi2016]循环之美(莫比乌斯反演，杜教筛)