问题 A: $Simple$

时间限制: 1 Sec 内存限制: 256 MB

题面

题面谢绝公开。

题解

不算数学的数学题？？

直接枚举会重。$60%$两种算法：1.无脑$vis$数组记录。2.$exgcd$解方程判定是否有解。

$100%$：首先考虑特殊情况：$n$、$m$互质。

我们设$n*x+m*y=z$，考虑枚举$y$和$x$，不难发现，当$y>=x$的时候均能找到一个$y'$使得$n|(y-y')$。

于是会出现重复。因此只需枚举$y([0,n-1])$，计算贡献即可。

对于一般情况，可以先化成互质。y筛到[0,n/gcd_{a,b}-1]即可。

#include<bits/stdc++.h>

#define rint register int

using namespace std;

int T;

long long n,m,q,ans;

inline long long gcd(long long A,long long B){return (B==)?A:gcd(B,A%B);}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        ans=;

        scanf("%lld %lld %lld",&n,&m,&q);

        long long g=gcd(n,m);

        for(rint i=;i<(n/g);++i)

        {

            long long z=q-i*m;

            if(z<)break;

            ans+=z/n+;

        }

        printf("%lld\n",q-ans+);

    }

}

巴特西

「题解」：$Simple$

问题 A: $Simple$

题面

题解

最新文章

热门文章