标签：CRT int 1000000000 cin Coprime Array
- 可以通过将x进行算术基本定理拆分后用CRT合并，弱化互素的条件，来推出答案序列长度至多为3的结论；也可以直接大胆假设
- 实现时可以通过随机化避免CRT
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int d;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int s,x;
cin>>s>>x;
if(__gcd(s,x)==1)
{
cout<<1<<endl;
cout<<s<<endl;
}
else
{
d=s/x*x;
s%=x;
int tmp=0,len=2;
if(s%2==1&&x%2==0)
{
tmp=1+d;
len++;
s--;
d=0;
}
int y,z;
while(1)
{
y=rand()%(x+1);
if(__gcd(y,x)==1&&abs(__gcd(s-y,x))==1)
{
z=s-y;
y=y+d;
if(y>1000000000)
{
z=z+(y-1000000000)/x*x;
y=y-(y-1000000000)/x*x;
if(y>1000000000)
{
y-=x;
z+=x;
}
if(z>1000000000)
{
cout<<-1<<endl;
return 0;
}
}
cout<<len<<endl;
if(len==2)
{
cout<<y<<" "<<z<<endl;
}
else
{
cout<<tmp<<" "<<y<<" "<<z<<endl;
}
return 0;
}
}
}
return 0;
}
标签：CRT,
int,
1000000000,
cin,
Coprime,
Array
From： https://www.cnblogs.com/watersail/p/18435581