#567991 (C++17) No.1262 グラフを作ろう！

提出ソース

結果

問題	No.1262 グラフを作ろう！
ユーザー	beet
提出日時	2020-10-16 22:57:33
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	2,543 ms / 3,000 ms
コード長	1,160 bytes
コンパイル時間	2,061 ms
コンパイル使用メモリ	204,636 KB
実行使用メモリ	207,652 KB
最終ジャッジ日時	2023-09-28 04:58:45
合計ジャッジ時間	145,261 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	970 ms 95,300 KB
testcase_01	AC	726 ms 76,976 KB
testcase_02	AC	1,508 ms 133,612 KB
testcase_03	AC	373 ms 48,988 KB
testcase_04	AC	1,865 ms 159,320 KB
testcase_05	AC	1,198 ms 112,424 KB
testcase_06	AC	2,356 ms 189,432 KB
testcase_07	AC	217 ms 33,428 KB
testcase_08	AC	2,005 ms 169,464 KB
testcase_09	AC	186 ms 31,696 KB
testcase_10	AC	618 ms 67,752 KB
testcase_11	AC	2,335 ms 188,216 KB
testcase_12	AC	799 ms 83,232 KB
testcase_13	AC	443 ms 55,764 KB
testcase_14	AC	725 ms 79,308 KB
testcase_15	AC	110 ms 21,732 KB
testcase_16	AC	1,822 ms 156,164 KB
testcase_17	AC	1,345 ms 123,020 KB
testcase_18	AC	1,794 ms 155,456 KB
testcase_19	AC	1,535 ms 139,056 KB
testcase_20	AC	2,367 ms 198,496 KB
testcase_21	AC	1,392 ms 131,728 KB
testcase_22	AC	1,361 ms 127,976 KB
testcase_23	AC	319 ms 45,232 KB
testcase_24	AC	1,910 ms 164,228 KB
testcase_25	AC	733 ms 79,884 KB
testcase_26	AC	923 ms 94,088 KB
testcase_27	AC	1,823 ms 156,684 KB
testcase_28	AC	1,455 ms 132,052 KB
testcase_29	AC	1,738 ms 149,644 KB
testcase_30	AC	896 ms 90,424 KB
testcase_31	AC	998 ms 98,304 KB
testcase_32	AC	987 ms 97,488 KB
testcase_33	AC	112 ms 21,872 KB
testcase_34	AC	2,351 ms 191,948 KB
testcase_35	AC	541 ms 63,992 KB
testcase_36	AC	82 ms 17,796 KB
testcase_37	AC	1,805 ms 156,308 KB
testcase_38	AC	1,531 ms 135,652 KB
testcase_39	AC	252 ms 38,508 KB
testcase_40	AC	519 ms 64,184 KB
testcase_41	AC	1,945 ms 165,072 KB
testcase_42	AC	2,043 ms 164,420 KB
testcase_43	AC	1,326 ms 117,308 KB
testcase_44	AC	1,057 ms 103,168 KB
testcase_45	AC	2,220 ms 182,832 KB
testcase_46	AC	2,403 ms 196,276 KB
testcase_47	AC	130 ms 23,648 KB
testcase_48	AC	2,008 ms 152,608 KB
testcase_49	AC	1,717 ms 148,720 KB
testcase_50	AC	1,924 ms 167,184 KB
testcase_51	AC	318 ms 44,832 KB
testcase_52	AC	2,200 ms 182,900 KB
testcase_53	AC	398 ms 53,760 KB
testcase_54	AC	737 ms 81,068 KB
testcase_55	AC	853 ms 90,620 KB
testcase_56	AC	1,822 ms 156,812 KB
testcase_57	AC	2,189 ms 185,832 KB
testcase_58	AC	590 ms 69,244 KB
testcase_59	AC	1,953 ms 167,096 KB
testcase_60	AC	2,033 ms 171,988 KB
testcase_61	AC	639 ms 71,612 KB
testcase_62	AC	1,435 ms 130,104 KB
testcase_63	AC	610 ms 69,712 KB
testcase_64	AC	816 ms 86,956 KB
testcase_65	AC	901 ms 94,144 KB
testcase_66	AC	694 ms 79,876 KB
testcase_67	AC	1,063 ms 107,920 KB
testcase_68	AC	2,372 ms 196,092 KB
testcase_69	AC	952 ms 98,492 KB
testcase_70	AC	2,281 ms 189,472 KB
testcase_71	AC	1,523 ms 136,428 KB
testcase_72	AC	2,160 ms 184,540 KB
testcase_73	AC	1,683 ms 143,432 KB
testcase_74	AC	1,041 ms 107,688 KB
testcase_75	AC	1,522 ms 140,644 KB
testcase_76	AC	1,423 ms 132,036 KB
testcase_77	AC	1,294 ms 123,300 KB
testcase_78	AC	1,638 ms 147,912 KB
testcase_79	AC	2,261 ms 188,252 KB
testcase_80	AC	2,341 ms 195,800 KB
testcase_81	AC	1,212 ms 117,932 KB
testcase_82	AC	1,394 ms 128,968 KB
testcase_83	AC	2,313 ms 183,220 KB
testcase_84	AC	1,580 ms 134,628 KB
testcase_85	AC	2,197 ms 185,916 KB
testcase_86	AC	1,519 ms 137,592 KB
testcase_87	AC	1,919 ms 166,916 KB
testcase_88	AC	1,214 ms 116,968 KB
testcase_89	AC	2,097 ms 173,892 KB
testcase_90	AC	2,540 ms 207,492 KB
testcase_91	AC	2,532 ms 207,436 KB
testcase_92	AC	2,517 ms 207,392 KB
testcase_93	AC	2,515 ms 207,440 KB
testcase_94	AC	2,480 ms 207,652 KB
testcase_95	AC	2,543 ms 207,652 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=Int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

vector<Int> totient_table(Int n){
  vector<Int> ts(n+1);
  iota(ts.begin(),ts.end(),0);
  for(Int i=2;i<=n;i++){
    if(ts[i]!=i) continue;
    for(Int j=i;j<=n;j+=i) ts[j]=ts[j]/i*(i-1);
  }
  return ts;
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n,m;
  cin>>n>>m;

  auto as=read(m);
  vector<Int> cnt(n+1,0);
  for(Int a:as) cnt[a]++;

  auto ts=totient_table(n+1);

  vector<vector<Int>> D(n+1);
  for(Int i=1;i<=n;i++)
    for(Int j=i;j<=n;j+=i)
      D[j].emplace_back(i);

  auto calc=[&](Int a){
    Int res=0;
    for(Int d:D[a]) res+=d*ts[a/d];
    return res-a;
  };

  Int ans=0;
  for(Int i=1;i<=n;i++)
    ans+=calc(i)*cnt[i];

  cout<<ans<<newl;
  return 0;
}

yukicoder

結果

テストケース

ソースコード