QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#738759#9167. Coprime Arrayucup-team134#RE 0ms4164kbC++171.5kb2024-11-12 19:52:122024-11-12 19:52:22

Judging History

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

  • [2024-11-12 19:52:22]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:4164kb
  • [2024-11-12 19:52:12]
  • 提交

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;
}
int main()
{
	int s,x;
	cin >> s >> x;
	if(__gcd(s,x)==1){
		printf("1\n%i\n",s);
		return 0;
	}
	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),pwrmod(c,mod-2));
			a+=c*treba;
			c*=p;
		}
		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();
	}
	printf("%i\n",sz(ans));
	for(auto p:ans)printf("%i ",p);
	printf("\n");
	return 0;
}

详细

Test #1:

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

input:

9 6

output:

3
1 7 1 

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
1 13 

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
148728581 851271419 

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
1 1 

result:

ok Correct

Test #5:

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

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: 3804kb

input:

48205845 903124530

output:

3
18811 48187033 1 

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
1 251037077 

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
1 30022919 

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
248711 63390587 

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
1 76579015 1 

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
1 40423667 1 

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
1 449277308 

result:

ok Correct

Test #14:

score: -100
Runtime Error

input:

81665969 919836918

output:


result: