結果
問題 | No.2249 GCDistance |
ユーザー | lddlinan |
提出日時 | 2023-03-17 22:48:20 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 714 ms / 5,000 ms |
コード長 | 1,210 bytes |
コンパイル時間 | 814 ms |
コンパイル使用メモリ | 86,116 KB |
実行使用メモリ | 170,012 KB |
最終ジャッジ日時 | 2023-10-18 15:50:08 |
合計ジャッジ時間 | 10,217 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 568 ms
169,344 KB |
testcase_01 | AC | 688 ms
170,012 KB |
testcase_02 | AC | 714 ms
170,012 KB |
testcase_03 | AC | 672 ms
170,012 KB |
testcase_04 | AC | 671 ms
169,628 KB |
testcase_05 | AC | 690 ms
170,012 KB |
testcase_06 | AC | 690 ms
170,012 KB |
testcase_07 | AC | 628 ms
170,012 KB |
testcase_08 | AC | 535 ms
169,364 KB |
testcase_09 | AC | 633 ms
170,012 KB |
testcase_10 | AC | 683 ms
170,008 KB |
ソースコード
#include<stdio.h> #include<string.h> #include<stdlib.h> #include <map> #include <vector> #include <queue> #include <deque> #include <set> #include <stack> #include <algorithm> #include <array> #include <unordered_set> #include <unordered_map> #include <string> using namespace std; bool rcmp(int a, int b) { return a>b; } typedef long long LL; LL ss[10000004]; char pmk[10000004]; LL fy[10000004]; #define MAXN 10000000 int ts[200004]; int main() { int n, i, j, p, c, cc, mx; LL r, x; int tc; scanf("%d", &tc); for (i=0; i<tc; i++) scanf("%d", &ts[i]); mx=0; for (i=0; i<tc; i++) mx=max(mx, ts[i]); memset(pmk, 0, mx+1); for (i=0; i<=mx; i++) fy[i]=1; for (i=2; i<=mx; i++) if (pmk[i]==0) { p=i; c=0; for (j=i; j<=mx; j+=i) { pmk[j]=1; c++; x=p-1; cc=c; while((cc%p)==0) { cc/=p; x*=p; } fy[j]*=x; } } ss[0]=0; ss[1]=0; for (i=2; i<=MAXN; i++) ss[i]=ss[i-1]+fy[i]; for (i=0; i<tc; i++) { n=ts[i]; // while(tc) { tc--; // scanf("%d", &n); // 0--n-1 r = n; r*=n-1; r/=2; r+=(r-ss[n]); printf("%lld\n", r); } return 0; }