[洛谷P4388] 付公主的矩形

18.09.09模拟赛T1。

一道数学题。

题目传送门

首先把对角线当成是某个点的移动轨迹，从左下到右上。

那么这个点每上升一个单位长度，就穿过一个格子。

每右移一个单位长度，也会穿过一个格子。

例外：穿过格点，会减少穿过的格子数。

初步的结论：R*C的矩形，对角线穿过的格子数N=R+C-gcd(R,C)。

那么我们只需算出这个方程的解的个数。

可以看出，R、C和gcd(R,C)都是gcd(R,C)的倍数。

那么N显然也是。

设N/gcd(R,C)=n，R/gcd(R,C)=r，C/gcd(R,C)=c。

方程两边同除gcd(R,C)：n=r+c-1。

由欧几里得算法可得：gcd(n+1,r)=gcd(n+1-r,r)=gcd( (r+c-1) +1-r,r)=gcd(c,r)。

这时候r和c一定是互质的，假如它们有公因数，在除以gcd(R,C)时就会被除掉。

所以：gcd(r,c)=1。得：gcd(n+1,r)=1。

即：n+1与r互质，n是N得因数。

答案即为：

所以我们线性筛出从2到n+1的欧拉函数phi [ i ]，挑出其中i-1是n的因数的，把它们的phi [ i ]加起来就行了。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,cnt,ans;

 int pr[];

 bool v[];

 int phi[];

 int main()

 {

     scanf("%d",&n);

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

     {

         if(!v[i])

         {

             pr[++cnt]=i;

             phi[i]=i-;

         }

         if(n%(i-)==)ans+=phi[i];

         for(int j=;(j<=cnt)&&(i*pr[j]<=n+);j++)

         {

             v[i*pr[j]]=true;

             if(i%pr[j]==)

             {

                 phi[i*pr[j]]=phi[i]*pr[j];

                 break;

             }else

             {

                 phi[i*pr[j]]=phi[i]*phi[pr[j]];

             }

         }

     }

     printf("%d",(ans+)/);

     return ;

 }

巴特西

[洛谷P4388] 付公主的矩形

最新文章

热门文章