CodeForces - 1089F Fractions (同余方程,互质数)
程序员文章站
2022-07-12 13:51:14
...
???????? ???????? ????????
第二个样例给了一点思路
#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";
}