ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

2267C　GCD Treasury

来源：Codeforces ★ 1500

本题活力0.71按难度、完成结果与训练证据估算

算法如山行则将至

查看原题王梓豪 的主页

题目描述

C. GCD Treasury
time limit per test2 seconds
memory limit per test256 megabytes

The greedy pirate Dimash found a treasury. It consists of n
piles of coins, numbered from 1
to n
. The i
-th pile contains exactly ai
coins. Pirate Dimash has a number x
that he can use to steal coins from the treasury. The stealing process works as follows:

First, he chooses an index 1≤i≤n
such that ai>0
and gcd
∗
(ai,x)≠1
. If there is no such index, the pirate stops.
Now let gcd(ai,x)
be g
. The pirate steals exactly g
coins from pile i
, after which ai
decreases by g
.
Finally, he sets x
to g
and continues stealing coins.
Your task is to help the pirate steal the maximum possible number of coins. Find the maximum number of coins that can be stolen from the treasury.

∗
gcd(ai,x)
denotes the greatest common divisor (GCD) of integers ai
and x
.

Input
Each test contains multiple test cases. The first line contains the number of test cases t
(1≤t≤104
). The description of the test cases follows.

The first line of each test case contains two integers n
and x
(1≤n,x≤3⋅105
) — the number of piles of coins in the treasury and the pirate's number.

The second line of each test case contains n
integers a1,a2,…an
(1≤ai≤3⋅105
).

It is guaranteed that the sum of n
over all test cases does not exceed 3⋅105
.

Output
For each test case, output one number — the maximum number of coins that can be stolen.

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int>zhishu(3e5+10, 0);
    for(int i = 2; i < 3e5+1; i++) {
        if(zhishu[i] == 0) {
            for(int j=2;j*i<3e5+1;j++) {
                zhishu[i*j]=1;
            }
        }
    }
    
    int t;
    cin>>t;
    while(t--) {
        int n,num;
        cin>>n>>num;
        vector<int> a(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        if(num == 1) {
            cout << 0 << endl;
            continue;
        }
        vector<int> g;
        int temp_num = num;
        for(int i = 2; i * i <= temp_num; i++) {
            if(zhishu[i]==0&&temp_num%i==0) {
                g.push_back(i);
                while(temp_num%i==0) {
                    temp_num/=i;
                }
            }
        }
        if(temp_num > 1) {
            g.push_back(temp_num);
        }
        long long maxans = 0;
        for(int j = 0; j < g.size(); j++) {
            long long temp = 0;
            for(int i = 0; i < n; i++) {
                if(a[i] % g[j] == 0) {
                    temp += a[i];
                }
            }
            maxans = max(temp, maxans);
        }
        
        cout<<maxans<<endl;
    }
}