DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選

Submission #7436067

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int gcd(int a,int b){
  if(!b) return a;
  return gcd(b,a%b);
}
int main(){
    ll n,k,A[200001];
    ll ans=0,x=0;
    cin>>n>>k;
    set<ll> B;
    map<ll,ll> C,D;
    rep(i,n) cin>>A[i],A[i]=gcd(k,A[i]),C[A[i]]++;
    for(int i=1;i<=sqrt(k);i++){
        if(k%i==0) B.insert(i),B.insert(k/i);
    }
    for(auto i:B)for(auto j:B) if(i*j%k==0) D[i]+=C[j];
    rep(i,n) ans+=D[A[i]];
    rep(i,n) if(A[i]*A[i]%k==0) ans--;
    cout<<ans/2;
}

Submission

Task問題 C - ロト2
User nameユーザ名 daiwakun
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 569 Byte
File nameファイル名
Exec time実行時間 151 ms
Memory usageメモリ使用量 2048 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 400 / 400 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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 76 ms 1792 KB
20_max_02.txt AC 70 ms 1792 KB
20_max_03.txt AC 88 ms 1792 KB
20_max_04.txt AC 72 ms 1792 KB
20_max_05.txt AC 99 ms 1792 KB
30_overflow_01.txt AC 66 ms 1792 KB
30_overflow_02.txt AC 66 ms 1792 KB
40_dmax_01.txt AC 150 ms 2048 KB
40_dmax_02.txt AC 150 ms 2048 KB
40_dmax_03.txt AC 151 ms 2048 KB
50_prime_01.txt AC 72 ms 1792 KB
50_prime_02.txt AC 79 ms 1792 KB
50_prime_03.txt AC 89 ms 1792 KB
60_prime_pow_01.txt AC 91 ms 1792 KB
60_prime_pow_02.txt AC 87 ms 1792 KB
60_prime_pow_03.txt AC 85 ms 1792 KB
70_one_01.txt AC 61 ms 1792 KB