QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686504#9167. Coprime Arrayucup-team4975#WA 0ms3712kbC++171.5kb2024-10-29 13:54:312024-10-29 13:54:35

Judging History

你现在查看的是最新测评结果

  • [2024-10-29 13:54:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3712kb
  • [2024-10-29 13:54:31]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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