Submission #4026019
Source Code Expand
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>
// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
using namespace std;
// types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
// solve
ll gcd(ll x, ll y){
if(x > y)return gcd(y, x);
if(x == 0)return y;
return gcd(y%x, x);
}
int main(int argc, char const* argv[])
{
int n;
ll k;
cin >> n >> k;
vector<ll> a(n);
rep(i, n)cin >> a[i];
vector<ll> kvec;
for(ll i = 2; i * i <= k; i++){
if(k % i == 0){
kvec.pb(i);
if(i * i != k)kvec.pb(k / i);
}
}
kvec.pb(1);
kvec.pb(k);
sort(kvec.begin(), kvec.end());
kvec.erase(unique(kvec.begin(), kvec.end()), kvec.end());
unordered_map<ll, int> mp;
rep(i, n)mp[gcd(k, a[i])]++;
rep(i, kvec.size()){
FOR(j, i+1, kvec.size()){
if(kvec[j] % kvec[i] == 0)mp[kvec[i]] += mp[kvec[j]];
}
}
ll res = 0;
rep(i, n){
ll tmp = k / gcd(k, a[i]);
res += mp[tmp];
if(gcd(k, a[i]) % tmp == 0)res--;
}
cout << res / 2 << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ロト2 |
User |
fumiphys |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1657 Byte |
Status |
AC |
Exec Time |
164 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 |
2 ms |
256 KB |
10_random_03.txt |
AC |
1 ms |
256 KB |
10_random_04.txt |
AC |
2 ms |
256 KB |
10_random_05.txt |
AC |
1 ms |
256 KB |
20_max_01.txt |
AC |
102 ms |
1792 KB |
20_max_02.txt |
AC |
97 ms |
1792 KB |
20_max_03.txt |
AC |
134 ms |
1792 KB |
20_max_04.txt |
AC |
95 ms |
1792 KB |
20_max_05.txt |
AC |
164 ms |
1792 KB |
30_overflow_01.txt |
AC |
95 ms |
1792 KB |
30_overflow_02.txt |
AC |
94 ms |
1792 KB |
40_dmax_01.txt |
AC |
139 ms |
1920 KB |
40_dmax_02.txt |
AC |
140 ms |
1920 KB |
40_dmax_03.txt |
AC |
140 ms |
1920 KB |
50_prime_01.txt |
AC |
101 ms |
1792 KB |
50_prime_02.txt |
AC |
120 ms |
1792 KB |
50_prime_03.txt |
AC |
131 ms |
1792 KB |
60_prime_pow_01.txt |
AC |
129 ms |
1792 KB |
60_prime_pow_02.txt |
AC |
130 ms |
1792 KB |
60_prime_pow_03.txt |
AC |
136 ms |
1792 KB |
70_one_01.txt |
AC |
72 ms |
1792 KB |