QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515830#9167. Coprime ArraySakuruaAC ✓1ms4164kbC++201.9kb2024-08-12 09:27:372024-08-12 09:27:37

Judging History

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

  • [2024-08-12 09:27:37]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4164kb
  • [2024-08-12 09:27:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
// #define int long long
#define endl "\n"
#define PII pair<int, int>
#define PDD pair<double, double>
#define PDI pair<double, int>
#define xx first
#define yy second
#define PI acos(-1)
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 7;
const int mod = 1e9 + 7; // 998244353

int biaoji[N], v[N], pri[N], idx;

void fast()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void getp(int x) // 欧拉筛
{
    for (int i = 2; i <= x; i++)
    {
        if (v[i] == 0)
        {
            v[i] = i;
            pri[idx++] = i;
        }
        for (int j = 1; j <= idx; j++)
        {
            if (pri[j] > v[i] || pri[j] > x / i)
            {
                break;
            }
            v[i * pri[j]] = pri[j];
        }
    }
}
signed main()
{
    fast();
    int n, s;
    cin >> n >> s;
    getp(1e5);

    if (__gcd(n, s) == 1)
    {
        cout << "1" << endl;
        cout << n << endl;
        return 0;
    }

    int i, j;
    if ((n % 2 == 1) && (s % 2 == 0))
    {
        for (i = 0; i < idx; i++)
        {
            if (__gcd(pri[i], s) == 1)
            {
                break;
            }
        }
        n -= pri[i];
        for (j = 0; j < idx; j++)
        {
            if (__gcd(abs(n - pri[j]), s) == 1 && __gcd(pri[j], s) == 1)
            {
                break;
            }
        }
        cout << 3 << endl;
        cout << pri[i] << ' ' << pri[j] << ' ' << n - pri[j] << endl;
    }
    else
    {
        for (i = 0; i < idx; i++)
        {
            if (__gcd(abs(n - pri[i]), s) == 1 && __gcd(pri[i], s) == 1)
            {
                break;
            }
        }
        cout << 2 << endl;
        cout << n - pri[i] << ' ' << pri[i] << endl;
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4116kb

input:

9 6

output:

3
5 5 -1

result:

ok Correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 4160kb

input:

14 34

output:

2
11 3

result:

ok Correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 4068kb

input:

1000000000 223092870

output:

2
999999971 29

result:

ok Correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 4136kb

input:

2 1000000000

output:

2
-1 3

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
649557653 11

result:

ok Correct

Test #6:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

33396678 777360870

output:

2
33396647 31

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
13 13 48205819

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
251037049 29

result:

ok Correct

Test #9:

score: 0
Accepted
time: 1ms
memory: 4160kb

input:

30022920 172746860

output:

2
30022917 3

result:

ok Correct

Test #10:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

63639298 808058790

output:

2
63639269 29

result:

ok Correct

Test #11:

score: 0
Accepted
time: 1ms
memory: 4092kb

input:

76579017 362768406

output:

3
5 5 76579007

result:

ok Correct

Test #12:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

40423669 121437778

output:

3
3 5 40423661

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
449277307 2

result:

ok Correct

Test #14:

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

input:

81665969 919836918

output:

3
5 5 81665959

result:

ok Correct

Test #15:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

470578680 280387800

output:

2
470578667 13

result:

ok Correct

Test #16:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

58450340 803305503

output:

2
58450330 10

result:

ok Correct

Test #17:

score: 0
Accepted
time: 1ms
memory: 4068kb

input:

125896113 323676210

output:

3
7 7 125896099

result:

ok Correct

Test #18:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

381905348 434752500

output:

2
381905317 31

result:

ok Correct

Test #19:

score: 0
Accepted
time: 1ms
memory: 4072kb

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

score: 0
Accepted
time: 1ms
memory: 4068kb

input:

35787885 270845190

output:

3
13 13 35787859

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed