QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#512577 | #9167. Coprime Array | ucup-team4361# | AC ✓ | 1ms | 3692kb | C++14 | 2.7kb | 2024-08-10 14:59:42 | 2024-08-10 14:59:44 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define F(i, j, k) for (int i = j; i <= k; ++i)
#define DF(i, j, k) for (int i = j; i >= k; --i)
using namespace std;
template <typename T> inline void read(T &n) {
T w = 1;
n = 0;
char ch = getchar();
while (!isdigit(ch) && ch != EOF) {
if (ch == '-') w = -1;
ch = getchar();
}
while (isdigit(ch) && ch != EOF) {
n = (n << 3) + (n << 1) + (ch & 15);
ch = getchar();
}
n *= w;
}
template <typename T> inline void write(T x) {
T l = 0;
ull y = 0;
if (!x) { putchar(48); return; }
if (x < 0) { x = -x; putchar('-'); }
while (x) { y = y * 10 + x % 10; x /= 10; ++l; }
while (l) { putchar(y % 10 + 48); y /= 10; --l; }
}
template <typename T> inline void writes(T x) {
write(x);
putchar(' ');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
}
template <typename T> inline void checkmax(T &a, T b) { a = a > b ? a : b; }
template <typename T> inline void checkmin(T &a, T b) { a = a < b ? a : b; }
inline bool isp(int x) {
if (x == 1) return false;
for (int i = 2; i * i <= x; i ++)
if (x % i == 0) return false;
return true;
}
inline int ksm(int x, int y, int z) {
int k = 1;
while (y) {
if (y & 1) k = (LL)k * x % z;
x = (LL)x * x % z;
y >>= 1;
}
return k;
}
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
int s, x;
read(s); read(x);
if (__gcd(s, x) == 1) {
cout << 1 << '\n';
cout << s << '\n';
return 0;
}
if ((s & 1) && !(x & 1)) {
cout << 3 << '\n';
cout << 1 << ' ';
s --;
}
else {
cout << '2' << '\n';
}
int ss = 1;
for (int i = 1; i * i <= x; i ++) {
if (x % i != 0) continue;
if (isp(i)) {
ss *= i;
}
if (i != x / i && isp(x / i)) {
ss *= (x / i);
}
}
int X = 0;
for (int i = 1; i * i <= x; i ++) {
if (x % i != 0) continue;
if (isp(i)) {
if (s % i != 1) X = (X + (LL)(ss / i) * ksm(ss / i, i - 2, i) % ss) % ss;
else X = (X + ss - (LL)(ss / i) * ksm(ss / i, i - 2, i) % ss) % ss;
}
if (i != x / i && isp(x / i)) {
if (s % (x / i) != 1) X = (X + (LL)(ss / (x / i)) * ksm(ss / (x / i), x / i - 2, x / i) % ss) % ss;
else X = (X + ss - (LL)(ss / (x / i)) * ksm(ss / (x / i), (x / i) - 2, (x / i)) % ss) % ss;
}
}
cout << X << ' ' << s - X << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
9 6
output:
3 1 1 7
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
14 34
output:
2 1 13
result:
ok Correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1000000000 223092870
output:
2 148728581 851271419
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 1000000000
output:
2 1 1
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
649557664 933437700
output:
2 83981 649473683
result:
ok Correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
33396678 777360870
output:
2 1 33396677
result:
ok Correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
48205845 903124530
output:
3 1 6271 48199573
result:
ok Correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
251037078 505905400
output:
2 1 251037077
result:
ok Correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
30022920 172746860
output:
2 1 30022919
result:
ok Correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
63639298 808058790
output:
2 248711 63390587
result:
ok Correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
76579017 362768406
output:
3 1 1 76579015
result:
ok Correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
40423669 121437778
output:
3 1 1 40423667
result:
ok Correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
449277309 720915195
output:
2 1 449277308
result:
ok Correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
81665969 919836918
output:
3 1 68069 81597899
result:
ok Correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3552kb
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: 3604kb
input:
125896113 323676210
output:
3 1 44461 125851651
result:
ok Correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
381905348 434752500
output:
2 1 381905347
result:
ok Correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
78916498 653897673
output:
1 78916498
result:
ok Correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
35787885 270845190
output:
3 1 1 35787883
result:
ok Correct
Extra Test:
score: 0
Extra Test Passed