Submission #6649111


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

long long int gcd(long long int a, long long int b) {
    if (a < b)swap(a, b);
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    LL N,K; cin >> N >> K;
    VL A(N); REP(i,N) cin >> A[i];

    map<LL,LL> div;

    for(LL i = 1; i * i <= K; i++){
        if(K % i == 0){
            if(i*i == K) div[i];
            else{
                div[i];
                div[K/i];
            }
        }
    }
    REP(i,N){
        div[gcd(A[i],K)]++;
    }
    LL ans = 0;
    for(auto p1 : div){
        for(auto p2 : div){
            dump(p1.first)
            dump(p2.first)
            if(p1.first > p2.first) continue;

            if(p1.first * p2.first % K == 0){
                if(p1.first != p2.first){
                    ans += p1.second * p2.second;
                }else{
                    ans += p1.second * (p1.second-1) / 2;
                }
            }
        }
    }
    cout << ans << endl;


}

Submission Info

Submission Time
Task C - ロト2
User Bloody_Yulii
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2369 Byte
Status AC
Exec Time 71 ms
Memory 1920 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 25
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_random_01.txt, 10_random_02.txt, 10_random_03.txt, 10_random_04.txt, 10_random_05.txt, 20_max_01.txt, 20_max_02.txt, 20_max_03.txt, 20_max_04.txt, 20_max_05.txt, 30_overflow_01.txt, 30_overflow_02.txt, 40_dmax_01.txt, 40_dmax_02.txt, 40_dmax_03.txt, 50_prime_01.txt, 50_prime_02.txt, 50_prime_03.txt, 60_prime_pow_01.txt, 60_prime_pow_02.txt, 60_prime_pow_03.txt, 70_one_01.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
10_random_01.txt AC 1 ms 256 KB
10_random_02.txt AC 1 ms 256 KB
10_random_03.txt AC 1 ms 256 KB
10_random_04.txt AC 1 ms 256 KB
10_random_05.txt AC 1 ms 256 KB
20_max_01.txt AC 32 ms 1792 KB
20_max_02.txt AC 30 ms 1792 KB
20_max_03.txt AC 42 ms 1792 KB
20_max_04.txt AC 29 ms 1792 KB
20_max_05.txt AC 47 ms 1792 KB
30_overflow_01.txt AC 31 ms 1792 KB
30_overflow_02.txt AC 30 ms 1792 KB
40_dmax_01.txt AC 71 ms 1920 KB
40_dmax_02.txt AC 71 ms 1920 KB
40_dmax_03.txt AC 71 ms 1920 KB
50_prime_01.txt AC 32 ms 1792 KB
50_prime_02.txt AC 36 ms 1792 KB
50_prime_03.txt AC 41 ms 1792 KB
60_prime_pow_01.txt AC 42 ms 1792 KB
60_prime_pow_02.txt AC 41 ms 1792 KB
60_prime_pow_03.txt AC 39 ms 1792 KB
70_one_01.txt AC 22 ms 1792 KB