QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#738780#9167. Coprime Arrayucup-team134#WA 0ms4084kbC++171.5kb2024-11-12 19:54:432024-11-12 19:54:52

Judging History

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

  • [2024-11-12 19:54:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4084kb
  • [2024-11-12 19:54:43]
  • 提交

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={1,1,s-1};
	}
	else{
		ans={1,s-1};
	}
	printf("%i\n",sz(ans));
	for(auto p:ans)printf("%i ",p);
	printf("\n");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

9 6

output:

3
1 1 7 

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
1 13 

result:

ok Correct

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3828kb

input:

1000000000 223092870

output:

2
1 999999999 

result:

wrong answer Element at position 2 is not coprime to x