QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#738845#9167. Coprime Arrayucup-team134#AC ✓0ms4088kbC++171.7kb2024-11-12 20:05:002024-11-12 20:05:03

Judging History

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

  • [2024-11-12 20:05:03]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4088kb
  • [2024-11-12 20:05:00]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;

mt19937 rng(time(NULL));

int mod=0;
int add(int a,int b){
    a+=b;
    if(a>=mod)
        a-=mod;
    return a;
}
int sub(int a,int b){
    a-=b;
    if(a<0)
        a+=mod;
    return a;
}
int mul(int a,int b){
    return (long long)a*b%mod;
}
int pwrmod(int x,int k){
    int ans=1;
    for(;k;k>>=1,x=mul(x,x))
        if(k&1)
            ans=mul(ans,x);
    return ans;
}
vector<int> solve(int s,int x){
	if(__gcd(s,x)==1){
		return {s};
	}
	vector<int> ps;
	int tr=x;
	for(int i=2;i*i<=tr;i++){
		if(tr%i==0){
			ps.pb(i);
			while(tr%i==0)tr/=i;
		}
	}
	if(tr!=1)ps.pb(tr);
	auto solve2=[&](){
		int a=0;
		int c=1;
		for(auto p:ps){
			int ost=s%p;
			ost=(p-ost)%p;
			int b=1;
			if((b+ost)%p==0){
				b++;
			}
			assert(b<p);
			mod=p;
			int treba=mul(sub(b,a%p),pwrmod(c%p,mod-2));
			a+=c*treba;
			c*=p;
		}
		//printf("%i\n",a);
		assert(__gcd(a,x)==1);
		assert(__gcd(abs(a-s),x)==1);
		vector<int> ret={a,-(a-s)};
		return ret;
	};
	vector<int> ans;
	if(ps[0]==2&&(s%2!=0)){
		s--;
		ans=solve2();
		ans.pb(1);
	}
	else{
		ans=solve2();
	}
	return ans;
}
int main()
{
	/*while(1){
		int s=rng()%1000+2,x=rng()%1000+2;
		printf("%i %i\n",s,x);
		solve(s,x);
	}*/
	int s,x;
	cin >> s >> x;
	auto ans=solve(s,x);
	printf("%i\n",sz(ans));
	for(auto p:ans)printf("%i ",p);
	printf("\n");
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

9 6

output:

3
1 7 1 

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
1 13 

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
148728581 851271419 

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
1 1 

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
83981 649473683 

result:

ok Correct

Test #6:

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

input:

33396678 777360870

output:

2
1 33396677 

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
18811 48187033 1 

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
1 251037077 

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
1 30022919 

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
248711 63390587 

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
1 76579015 1 

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
1 40423667 1 

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
1 449277308 

result:

ok Correct

Test #14:

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

input:

81665969 919836918

output:

3
68069 81597899 1 

result:

ok Correct

Test #15:

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

input:

470578680 280387800

output:

2
1 470578679 

result:

ok Correct

Test #16:

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

input:

58450340 803305503

output:

2
1 58450339 

result:

ok Correct

Test #17:

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

input:

125896113 323676210

output:

3
59281 125836831 1 

result:

ok Correct

Test #18:

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

input:

381905348 434752500

output:

2
1 381905347 

result:

ok Correct

Test #19:

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

input:

78916498 653897673

output:

1
78916498 

result:

ok Correct

Test #20:

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

input:

35787885 270845190

output:

3
1 35787883 1 

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed