HDU - 5970 题解

题目链接

HDU - 5970

分析

很显然\(f(x,y)\)与\(f(x+y*k,y)\)的结果相同，因为它们在第一次取模后会变成相同的式子

我们再看一下数据的范围，突破口肯定在\(m\)那里

那么我们就可以从m开始枚举，对于每一个m，我们分别求出模\(m\)等于\(0,1,2......m-1\)的\(f\)值

那么我们就可以把所有模\(m\)的值相同的数放在一起单独处理

对于每一个单独处理的数列，我们不能简单地进行求和处理，因为会涉及到向下取整的操作

其实，我们再推算一下,\(f(i,j)=gcd(i,j)*gcd(i,j)*c\)

而最后的结果是\(\frac{i*j}{f(i,j)}=\frac{i*j}{gcd(i,j)*gcd(i,j)*c}\)

\(i\)和\(j\)肯定能被\(gcd(i,j)\)整除，所以向下取整一定是以\(c\)为周期的

那我们可以再把这一个数列分成\(c\)个等差数列来处理

首项、公差、项数都非常显然，简单推导就可以得到

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,m,mod;

ll my_gcd(int aa,int bb,int &g,int &c){

    c=0,g=aa;

    int t;

    while(bb>0){

        c++;

        t=aa%bb;

        aa=bb;

        bb=t;

    }

    g=aa;

    return 1ll*aa*aa*c;

}

void solve(){

    ll ans=0;

    int g,c;

    for(int j=1;j<=m;j++){

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

            ll now=my_gcd(i,j,g,c);

            for(int k=0;k<c;k++){

                if(i+k*j>n) break;

                ll a0=(i+k*j)*j/now;

                ll d=c*j*j/now;

                ll num=(n-(i+k*j))/(c*j)+1;

                ans=((ans+a0*num)%mod+num*(num-1)/2%mod*d%mod)%mod;

            }

        }

    }

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

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

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

        solve();

    }

    return 0;

}

巴特西

HDU - 5970 题解

题目链接

分析

代码

最新文章

热门文章