P4388 付公主的矩形(gcd+欧拉函数)

P4388 付公主的矩形

前置芝士

$gcd$与欧拉函数

要求对其应用于性质比较熟，否则建议左转百度

思路

有$n×m$的矩阵，题目要求对角线经过的格子有$N$个，

设函数$f(x,y)$为矩阵$(x,y)$对角线经过的格子

设$gcd(n,m)=1$，对角线在矩形中不会经过任意一个格点，$f(n,m)=n+m-1$

那$gcd(n,m)!=1$呢？将这个矩阵拆除$gcd(n,m)$个相同的矩阵

其中$gcd(n',m')=1$，则$\dfrac{n}{n'}=\dfrac{m}{m'}$

所以我们能推倒出公式

$f(n,m)=\dfrac{n}{n'}f(n',m')$

$~~~~~~~~~~~~~=\dfrac{n}{n'}×(n'+m'-1)$

$~~~~~~~~~~~~~=\dfrac{n×n'}{n'}+\dfrac{m×m'}{m'}-gcd(n,m)$

$~~~~~~~~~~~~~=n+m-gcd(n,m)$

则我们要求$(n,m)$的对数使得 $n+m-gcd(n,m)=N$

设$i=gcd(n,m)$

$n+m-gcd(n,m)=N $

$\Rightarrow \dfrac{n}{i}+\dfrac{m}{i}-1=\dfrac{N}{i}$

$\Rightarrow \dfrac{n}{i}+\dfrac{m}{i}=\dfrac{N}{i}+1$

我们枚举$gcd(n,m)$也就是$i$，那我们怎么求呢？

欧拉函数有一性质$\varphi(N)$，$N>2$时，$\varphi(N)$为偶数

所以$nun=\varphi(\dfrac{N}{i}+1)$

跑得比较慢(200ms)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL maxn=1000007;

LL n,tot,ans;

LL phi[maxn],pim[maxn>>1];

inline void First(){

    for(LL i=2;i<=n+1;i++){

        if(!phi[i])

            phi[i]=i-1,

            pim[++tot]=i;

        for(LL j=1;j<=tot&&pim[j]*i<maxn;j++)

        	if(i%pim[j]==0){

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

                break;

            }else

                phi[i*pim[j]]=phi[i]*(pim[j]-1);

    }

}

int main () {

    scanf("%lld",&n);

    First();

    for(LL i=1;i<=n;i++)

        if(n%i==0)

            ans+=phi[n/i+1];

    printf("%lld",ans+1>>1);

    return 0;

}

剪一下枝(100ms)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Read(){

    int x=0,f=1; char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-') f=-1; c=getchar();

    }

    while(c>='0'&&c<='9')

        x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*f;

}

const LL maxn=1000007;

int n,tot;

int phi[maxn],pim[maxn>>1];

LL ans;

inline void First(){

    for(int i=2;i<=n+1;i++){

        if(!phi[i])

            phi[i]=i-1,

            pim[++tot]=i;

        for(int j=1;j<=tot&&pim[j]*i<maxn;j++)

        	if(i%pim[j]==0){

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

                break;

            }else

                phi[i*pim[j]]=phi[i]*(pim[j]-1);

    }

}

int main () {

    n=Read();

    First();

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

        if(n%i==0)

            if(i*i==n)

                ans+=phi[i+1];

            else

                ans+=phi[i+1]+phi[n/i+1];

    printf("%lld",ans+1>>1);

    return 0;

}

巴特西

P4388 付公主的矩形(gcd+欧拉函数)

前置芝士

思路

最新文章

热门文章