結果
問題 | No.2249 GCDistance |
ユーザー |
![]() |
提出日時 | 2023-03-17 22:01:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,635 ms / 5,000 ms |
コード長 | 668 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 32,256 KB |
実行使用メモリ | 159,488 KB |
最終ジャッジ日時 | 2024-09-18 11:00:40 |
合計ジャッジ時間 | 20,934 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
コンパイルメッセージ
main.cpp:3:5: warning: built-in function 'free' declared as non-function [-Wbuiltin-declaration-mismatch] 3 | int free[10000010],prime[10000010]; | ^~~~
ソースコード
#include <stdio.h>int free[10000010],prime[10000010];long long int count[10000010];int main(){for(int i=2;i<=10000000;i++) if(prime[i]==0) for(int j=i;j<=10000000;j+=i) prime[j]++;for(int i=2;i<=10000;i++) for(int j=i*i;j<=10000000;j+=i*i) free[j] = 1;for(int i=1;i<=10000000;i++){if(free[i]==0){int C = 0;for(int j=i;j<=10000000;j+=i){C++;if(prime[i]%2==0) count[j] += C;else count[j] -= C;}}}count[1]--;for(int i=1;i<=10000000;i++) count[i] += count[i-1];int T;scanf("%d",&T);while(T--){long long int a;scanf("%lld",&a);long long int ans = a*(a-1);printf("%lld\n",ans - count[a]);}}