Submission #172490


Source Code Expand

Copy
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

// 最大公約数
int gcd(int a, int b){
    while(b != 0){
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}


int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i=0; i<n; ++i)
        cin >> a[i];

    map<int, long long> dp, ret;
    for(int i=0; i<n; ++i){
        map<int, long long> nextDp;
        nextDp[a[i]] = 1;
        for(const auto& p : dp)
            nextDp[gcd(p.first, a[i])] += p.second;
        for(const auto& p : nextDp)
            ret[p.first] += p.second;
        dp.swap(nextDp);
    }

    for(int i=0; i<m; ++i){
        int x;
        cin >> x;
        cout << ret[x] << endl;
    }

    return 0;
}

Submission Info

Submission Time
Task D - GCD区間
User mamekin
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1112 Byte
Status AC
Exec Time 856 ms
Memory 7588 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 30
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 21 ms 928 KB
subtask0_sample_02.txt AC 21 ms 804 KB
subtask0_sample_03.txt AC 21 ms 800 KB
subtask1_01.txt AC 28 ms 924 KB
subtask1_02.txt AC 27 ms 924 KB
subtask1_03.txt AC 27 ms 928 KB
subtask1_04.txt AC 768 ms 7588 KB
subtask1_05.txt AC 795 ms 7588 KB
subtask1_06.txt AC 79 ms 1308 KB
subtask1_07.txt AC 54 ms 1304 KB
subtask1_08.txt AC 54 ms 1184 KB
subtask1_09.txt AC 138 ms 1184 KB
subtask1_10.txt AC 138 ms 1248 KB
subtask1_11.txt AC 856 ms 7580 KB
subtask1_12.txt AC 100 ms 1116 KB
subtask1_13.txt AC 152 ms 1196 KB
subtask1_14.txt AC 79 ms 1112 KB
subtask1_15.txt AC 110 ms 1188 KB
subtask1_16.txt AC 137 ms 1200 KB
subtask1_17.txt AC 147 ms 1304 KB
subtask1_18.txt AC 87 ms 1312 KB
subtask1_19.txt AC 85 ms 1196 KB
subtask1_20.txt AC 83 ms 1184 KB
subtask1_21.txt AC 76 ms 1180 KB
subtask1_22.txt AC 81 ms 1316 KB
subtask1_23.txt AC 91 ms 1312 KB
subtask1_24.txt AC 80 ms 1180 KB
subtask1_25.txt AC 81 ms 1192 KB
subtask1_26.txt AC 533 ms 7204 KB
subtask1_27.txt AC 618 ms 7572 KB