QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#512318#9167. Coprime Arrayucup-team3723#RE 2ms7060kbC++201.4kb2024-08-10 14:08:292024-08-10 14:08:30

Judging History

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

  • [2024-08-11 17:38:28]
  • hack成功,自动添加数据
  • (/hack/775)
  • [2024-08-10 14:08:30]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:7060kb
  • [2024-08-10 14:08:29]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    const int ma = 1e6;
    int s, x;
    cin >> s >> x;
    if (__gcd(s, x) == 1)
    {
        cout << "1\n";
        cout << s << endl;
    }
    else
    {
        vector<int> isp(ma + 1, 1);
        int tmpx = x;
        isp[0] = isp[1] = 0;
        for (int i = 2; i * i <= x; ++i)
        {
            if (x % i) continue;
            while (x % i == 0) x /= i;
            for (int j = 1; i * j <= ma; ++j) isp[i * j] = 0;
        }
        if (x != 1) for (int i = 1; i * x <= ma; ++i) isp[i * x] = 0;
        vector<int> ans;
        if (s % 2)
        {
            ans.push_back(1);
            --s;
        }
        isp[1] = 1;
        for (int i = 1; i < min(ma, s); ++i)
        {
            int g1 = __gcd(i, s), g2 = __gcd(s - i, s);
            if (g1 == 1 && g2 == 1)
            {
                if (isp[i] && isp[s - i])
                {
                    ans.push_back(i);
                    ans.push_back(s - i);
                    break;
                }
                if (s + i <= ma && isp[i] && isp[s + i])
                {
                    ans.push_back(-i);
                    ans.push_back(s + i);
                    break;
                }
            }
        }
        cout << ans.size() << endl;
        for (auto v : ans) cout << v << ' ';
        cout << endl;
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 6900kb

input:

9 6

output:

3
1 1 7 

result:

ok Correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 7060kb

input:

14 34

output:

2
1 13 

result:

ok Correct

Test #3:

score: -100
Runtime Error

input:

1000000000 223092870

output:


result: