QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#512026 | #9167. Coprime Array | ucup-team055# | AC ✓ | 0ms | 3880kb | C++20 | 2.0kb | 2024-08-10 13:18:55 | 2024-10-14 07:51:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using ll = long long;
//a*x+b*y=gcd(a,b)となるx,yにする 返り値gcd(a,b)
ll Euclid(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return a;
}
ll d=Euclid(b,a%b,y,x);
y-=a/b*x;
return d;
}
// val1=(a,p) val2=(b,q)
// return (c,r)
// c: c%p==a && c%q==b
// r: r=lcm(p,q)
// need: a%gcd(p,q)==b%gcd(p,q)
// use: Euclid
std::pair<long long,long long> ctr_sub(std::pair<long long,long long> val1,std::pair<long long,long long> val2){
long long a,b,p,q;
long long X,Y,G,ans_val,ans_mod;
tie(a,p)=val1;
tie(b,q)=val2;
if(p<q) swap(a,b),swap(p,q);
G=Euclid(p,q,X,Y);
if((b-a)%G!=0) return {-1,-1};
ans_mod=p*(q/G);
ans_val=(p*((X*((b-a)/G))%q))%ans_mod+a;
return {(ans_val%ans_mod+ans_mod)%ans_mod,ans_mod};
}
void solve(){
ll s, x;
cin >> s >> x;
ll X = x;
vector<ll> p;
ll tmp = 2;
while (x >= tmp * tmp){
if (x % tmp == 0){
p.push_back(tmp);
while (x % tmp == 0) x /= tmp;
}
tmp++;
}
if (x != 1) p.push_back(x);
if (gcd(s, X) == 1){
cout << "1\n" << s << "\n";
return;
}
ll N = 2;
if (s % 2 == 1 && X % 2 == 0) N = 3;
vector q(p.size(), vector<pair<ll, ll>>(N));
rep(i, 0, p.size()){
rep(j, 0, N - 1) q[i][j].first = 1;
q[i][N - 1].first = (s % p[i] + p[i] - N + 1) % p[i];
if (q[i][N - 1].first == 0){
q[i][N - 1].first = p[i] - 1;
q[i][0].first = 2 % p[i];
}
rep(j, 0, N) q[i][j].second = p[i];
}
cout << N << "\n";
ll sum = 0;
rep(i, 0, N - 1){
rep(j, 1, p.size()){
q[0][i] = ctr_sub(q[0][i], q[j][i]);
}
cout << q[0][i].first << " ";
sum += q[0][i].first;
}
cout << s - sum << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
9 6
output:
3 1 1 7
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
14 34
output:
2 1 13
result:
ok Correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
1000000000 223092870
output:
2 148728581 851271419
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
2 1000000000
output:
2 1 1
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
649557664 933437700
output:
2 83981 649473683
result:
ok Correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
33396678 777360870
output:
2 1 33396677
result:
ok Correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
48205845 903124530
output:
3 18811 1 48187033
result:
ok Correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
251037078 505905400
output:
2 1 251037077
result:
ok Correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
30022920 172746860
output:
2 1 30022919
result:
ok Correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
63639298 808058790
output:
2 248711 63390587
result:
ok Correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
76579017 362768406
output:
3 1 1 76579015
result:
ok Correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3644kb
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: 3644kb
input:
81665969 919836918
output:
3 68069 1 81597899
result:
ok Correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
470578680 280387800
output:
2 1 470578679
result:
ok Correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
58450340 803305503
output:
2 1 58450339
result:
ok Correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
125896113 323676210
output:
3 59281 1 125836831
result:
ok Correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
381905348 434752500
output:
2 1 381905347
result:
ok Correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
78916498 653897673
output:
1 78916498
result:
ok Correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
35787885 270845190
output:
3 1 1 35787883
result:
ok Correct
Extra Test:
score: 0
Extra Test Passed