QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686504 | #9167. Coprime Array | ucup-team4975# | WA | 0ms | 3712kb | C++17 | 1.5kb | 2024-10-29 13:54:31 | 2024-10-29 13:54:35 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N=100010;
int n;
ll ai[N],mi[N];
ll mul(ll a,ll b,ll m) {
ll res=0;
while(b>0) {
if(b&1) res=(res+a)%m;
a=(a+a)%m;
b>>=1;
}
return res;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y) {
if (b==0) {
x=1;y=0;return a;
}
ll d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll excrt() {
ll x,y;
ll m1=mi[1],a1=ai[1];
ll ans=(a1%m1+m1)%m1;
for(int i=2;i<=n;i++) {
ll a2=ai[i],m2=mi[i];
ll a=m1,b=m2,c=(a2-a1%m2+m2)%m2;
ll d=extend_gcd(a,b,x,y);
if(c%d!=0) return -1;
x=mul(x,c/d,b/d);
ans=a1+x*m1;
m1=m2/d*m1;
ans=(ans%m1+m1)%m1;
a1=ans;
}
return ans;
}
int s,x;
int solve(int s,int x) {
//cout<<333<<endl;
for(int i=2;i*i<=x;i++) {
if(x%i==0) {
while(x%i==0) x/=i;
mi[++n]=i;
}
}
//cout<<222<<endl;
for(int i=1;i<=n;i++) {
ai[i]=1;
if(s%mi[1]==1) ai[i]=2;
}
//cout<<111<<endl;
return excrt();
}
int solve1() {
//cout<<333<<endl;
for(int i=2;i*i<=x;i++) {
if(x%i==0) {
while(x%i==0) x/=i;
mi[++n]=i;
}
}
//cout<<222<<endl;
for(int i=1;i<=n;i++) {
ai[i]=1;
if(mi[i]%2) {
if(s%mi[i]==2) ai[i]=2;
}
}
//cout<<111<<endl;
return excrt();
}
signed main() {
cin>>s>>x;
if(__gcd(s,x)==1) {
cout<<1<<endl;
cout<<s<<endl;
}
else if(x%2==1 || s%2==0) {
int t=solve(s,x);
cout<<2<<endl;
cout<<t<<" "<<s-t<<endl;
}
else {
int t=solve1();
cout<<3<<endl;
cout<<t<<" "<<t<<" "<<s-2*t<<endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
9 6
output:
3 1 1 7
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
14 34
output:
2 1 13
result:
ok Correct
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
1000000000 223092870
output:
2 1 999999999
result:
wrong answer Element at position 2 is not coprime to x