长乐集训DAY13

上午&下午
全都爆蛋了

P1390 公约数的和
[https://www.luogu.com.cn/problem/P1516](P1516 青蛙的约会 "P1516 青蛙的约会")
代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int ans,n,f[2000005];
int gcd(int a,int b)
{
    if(b==0)
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);
    }
}
signed main()
{
    cin>>n;
    if(n<=2000)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                ans+=gcd(i,j);
            }
        }
        cout<<ans<<endl;
    }
    else
    {
        for(int i=n;i>0;i--)
        {
//          f[i]=(n*n)/(i*i);
            f[i]=n/i*(n/i);
            for(int j=i<<1;j<=n;j+=i)
            {
//              cout<<i<<"   "<<j<<endl;
                f[i]-=f[j];
//              j*=2;
            }
            ans+=f[i]*i;
        }
        cout<<(ans-(n*n+n)/2)/2<<endl;
    }

}

模板题，把gcd算法稍微改一下，gcd的同时顺便求出方程的一组解就完了
代码

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int xx,yy,m,n,l,x,y,a,b,g;
int exgcd(int aa,int bb,int& xx,int& yy)
{
    if(!bb)
    {
        xx=1;
        yy=0;
        g=aa;
    }
    else
    {
        exgcd(bb,aa%bb,yy,xx);
        yy-=(aa/bb)*xx;
    }
}
signed main()
{
    cin>>x>>y>>m>>n>>l;
    a=n-m;
    b=x-y;
    if(a<0)
    {
        a=-a;
        b=-b;
    }
    exgcd(a,l,xx,yy);
    if(b%g!=0)
    {
        cout<<"Impossible"<<endl;
    }
    else
    {
        cout<<(b/g*xx%(l/g)+l/g)%(l/g)<<endl;
    }
}