QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515846#9167. Coprime ArraySakuruaAC ✓1ms4564kbC++201.9kb2024-08-12 09:50:522024-08-12 09:50:52

Judging History

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

  • [2024-08-12 09:50:52]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4564kb
  • [2024-08-12 09:50:52]
  • 提交

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 = 1e6 + 7;
const int mod = 1e9 + 7; // 998244353

int biaoji[N], v[N] = {1, 1}, pri[N], idx;

void fast()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int x = 1e5;
void getp() // 欧拉筛
{
    for (int i = 2; i <= x; i++)
    {
        if (v[i] == 0)
        {
            pri[++idx] = i;
        }

        for (int j = 1; j <= idx; j++)
        {
            if (i * pri[j] > x)
            {
                break;
            }

            v[i * pri[j]] = 1;

            if (i % pri[j] == 0)
                break;
        }
    }
}
signed main()
{
    fast();
    int n, s;
    cin >> n >> s;
    getp();
    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: 4564kb

input:

9 6

output:

3
5 5 -1

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
11 3

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
999999971 29

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
-1 3

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
649557653 11

result:

ok Correct

Test #6:

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

input:

33396678 777360870

output:

2
33396647 31

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
13 13 48205819

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
251037049 29

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
30022917 3

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
63639269 29

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
5 5 76579007

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
3 5 40423661

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
449277307 2

result:

ok Correct

Test #14:

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

input:

81665969 919836918

output:

3
5 5 81665959

result:

ok Correct

Test #15:

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

input:

470578680 280387800

output:

2
470578667 13

result:

ok Correct

Test #16:

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

input:

58450340 803305503

output:

2
58450309 31

result:

ok Correct

Test #17:

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

input:

125896113 323676210

output:

3
7 7 125896099

result:

ok Correct

Test #18:

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

input:

381905348 434752500

output:

2
381905317 31

result:

ok Correct

Test #19:

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

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

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

input:

35787885 270845190

output:

3
13 13 35787859

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed