luogu4388 付公主的矩形

题面：

为了排解心中的怒气，她造了大量的稻草人来发泄。每天付公主都会把一些稻草人摆成一个R∗C的矩形，矩形的每个方格上都有一个稻草人。然后她站在这个矩形的左上角，向矩形的右下角射箭。付公主的箭术过人，她能穿透任意多的稻草人。弓箭经过的方格上的稻草人难逃厄运，报废掉了。看着被毁坏的稻草人，付公主开心了一些。

但是制造稻草人需要大量的金钱，所以付公主不希望坏掉太多的稻草人，所以她每天都选择毁坏掉N个稻草人。付公主还是个喜新厌旧的人，她希望每天能看到一种不同的稻草人摆放矩形。矩形是可以旋转的，即R∗C和C∗R等价。她毫不费力地算出了摆放方案数，于是她决定刁难你一下。不甘示弱的你决定写个程序计算这个数来提交付公主的答卷。

数学题。。。

（懵逼*INF）

！震惊，竟是欧拉函数！

先分析一下，对于一对a、b，经过的格数为 a+b-gcd(a,b)，具体证明：

每向右移一个则+1；

每向下移一个则+1；

每经过一个整点则-1；

因此为a+b-gcd(a,b);

因此有n = a+b-gcd(a,b);(易证gcd是n的约数)

同除gcd(a,b)，得

(n/gcd(a,b)) = a+b-1;（这里a = a/gcd(a,b),b = b/gcd(a,b)）

设m=n/gcd(a,b);

m+1 = a+b;

这里m是n的因数，a、b互质。

找n的因数，再加一，求欧拉函数，求和。

但是会有重复（a、b是一对），所以ans先加一再>>1。（+1是a=n,b=n只算了一次）

代码：

#include<cstdio>

#define N 100000050

int n,cri[N],phi[N],cnt;

bool vis[N];

int ans = ;

void oula()

{

    phi[] = ;

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

    {

        if(!vis[i])

        {

            phi[i]=i-;

            cri[++cnt] = i;

        }

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

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

        {

            vis[i*cri[j]]=;

            if(i%cri[j]==)

            {

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

                break;

            }else

            {

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

            }

        }

    }

}

int main()

{

//    freopen("chord.in","r",stdin);

//    freopen("chord.out","w",stdout);

    scanf("%d",&n);

    oula();

    printf("%d\n",(ans+)>>);

    return ;

}

巴特西

luogu4388 付公主的矩形

最新文章

热门文章