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 |
|
|
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 |