欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CodeForces - 1089F Fractions (同余方程,互质数)

程序员文章站 2022-07-12 13:51:14
...

????‍???? ????‍???? ????‍????
第二个样例给了一点思路
CodeForces - 1089F Fractions (同余方程,互质数)

#define int ll
inline void solve()
{
    int n;cin>>n;
    int flag=0;
    for(int i=2;i*i<=n;++i)
    {
        if(flag) break;
        if(n%i==0&&__gcd(i,n/i)==1)
        {
            int x=i,y=n/i;
            for(int a=1;a<x;++a)
            {
                if(n-1-a*x>0&&((n-1-a*y)%x==0))
                {
                    int b=(n-1-a*y)/x;
                    cout<<"YES\n";
                    cout<<2<<endl;
                    cout<<a<<" "<<x<<endl;
                    cout<<b<<" "<<y<<endl;
                    flag=1;
                    break;
                }
            }
        }
    }
    if(!flag) cout<<"NO\n";
}