QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#686534#9167. Coprime Arrayucup-team4975#AC ✓0ms3692kbC++171.6kb2024-10-29 14:05:432024-10-29 14:05:47

Judging History

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

  • [2024-10-29 14:05:47]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3692kb
  • [2024-10-29 14:05:43]
  • 提交

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;
		}
	}
	if(x>1) mi[++n]=x;
	//cout<<222<<endl;
	for(int i=1;i<=n;i++) {
		ai[i]=1;
		if(s%mi[i]==1) ai[i]=2;
	}
	//cout<<111<<endl;
	/*for(int i=1;i<=n;i++) {
		cout<<mi[i]<<" "<<ai[i]<<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;
		}
	}
	if(x>1) mi[++n]=x;
	//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;
		}
	}
	
	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;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

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: 0
Accepted
time: 0ms
memory: 3692kb

input:

1000000000 223092870

output:

2
148728581 851271419

result:

ok Correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2 1000000000

output:

2
1 1

result:

ok Correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

649557664 933437700

output:

2
83981 649473683

result:

ok Correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

33396678 777360870

output:

2
1 33396677

result:

ok Correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

48205845 903124530

output:

3
18811 18811 48168223

result:

ok Correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

251037078 505905400

output:

2
1 251037077

result:

ok Correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

30022920 172746860

output:

2
1 30022919

result:

ok Correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

63639298 808058790

output:

2
248711 63390587

result:

ok Correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

76579017 362768406

output:

3
1 1 76579015

result:

ok Correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

40423669 121437778

output:

3
1 1 40423667

result:

ok Correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

449277309 720915195

output:

2
1 449277308

result:

ok Correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

81665969 919836918

output:

3
68069 68069 81529831

result:

ok Correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

470578680 280387800

output:

2
1 470578679

result:

ok Correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

58450340 803305503

output:

2
1 58450339

result:

ok Correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

125896113 323676210

output:

3
59281 59281 125777551

result:

ok Correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

381905348 434752500

output:

2
1 381905347

result:

ok Correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

35787885 270845190

output:

3
1 1 35787883

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed