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

提出ソース

結果

問題	No.1262 グラフを作ろう！
ユーザー	beet
提出日時	2020-10-16 22:57:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,618 ms / 3,000 ms
コード長	1,160 bytes
コンパイル時間	2,615 ms
コンパイル使用メモリ	207,004 KB
実行使用メモリ	207,488 KB
最終ジャッジ日時	2024-07-20 23:31:30
合計ジャッジ時間	148,045 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	937 ms 95,440 KB
testcase_01	AC	690 ms 77,056 KB
testcase_02	AC	1,439 ms 133,856 KB
testcase_03	AC	346 ms 49,176 KB
testcase_04	AC	1,838 ms 159,360 KB
testcase_05	AC	1,127 ms 112,304 KB
testcase_06	AC	2,272 ms 189,568 KB
testcase_07	AC	186 ms 33,628 KB
testcase_08	AC	1,941 ms 169,600 KB
testcase_09	AC	177 ms 31,716 KB
testcase_10	AC	565 ms 67,712 KB
testcase_11	AC	2,351 ms 188,220 KB
testcase_12	AC	789 ms 83,484 KB
testcase_13	AC	425 ms 55,808 KB
testcase_14	AC	711 ms 79,488 KB
testcase_15	AC	108 ms 21,888 KB
testcase_16	AC	1,833 ms 156,368 KB
testcase_17	AC	1,372 ms 122,892 KB
testcase_18	AC	1,771 ms 155,904 KB
testcase_19	AC	1,517 ms 139,216 KB
testcase_20	AC	2,428 ms 198,876 KB
testcase_21	AC	1,355 ms 131,968 KB
testcase_22	AC	1,408 ms 128,128 KB
testcase_23	AC	307 ms 45,312 KB
testcase_24	AC	1,926 ms 164,416 KB
testcase_25	AC	744 ms 79,872 KB
testcase_26	AC	902 ms 94,528 KB
testcase_27	AC	1,774 ms 156,672 KB
testcase_28	AC	1,458 ms 132,348 KB
testcase_29	AC	1,708 ms 149,800 KB
testcase_30	AC	840 ms 90,736 KB
testcase_31	AC	936 ms 98,560 KB
testcase_32	AC	926 ms 97,524 KB
testcase_33	AC	97 ms 21,812 KB
testcase_34	AC	2,286 ms 192,060 KB
testcase_35	AC	490 ms 64,128 KB
testcase_36	AC	76 ms 17,920 KB
testcase_37	AC	1,820 ms 156,560 KB
testcase_38	AC	1,556 ms 135,808 KB
testcase_39	AC	249 ms 38,760 KB
testcase_40	AC	536 ms 63,872 KB
testcase_41	AC	1,972 ms 165,120 KB
testcase_42	AC	1,900 ms 164,480 KB
testcase_43	AC	1,177 ms 117,632 KB
testcase_44	AC	975 ms 103,296 KB
testcase_45	AC	2,112 ms 183,028 KB
testcase_46	AC	2,338 ms 196,608 KB
testcase_47	AC	123 ms 23,772 KB
testcase_48	AC	1,752 ms 152,844 KB
testcase_49	AC	1,680 ms 148,992 KB
testcase_50	AC	1,927 ms 167,160 KB
testcase_51	AC	295 ms 45,056 KB
testcase_52	AC	2,188 ms 183,068 KB
testcase_53	AC	360 ms 53,964 KB
testcase_54	AC	682 ms 81,144 KB
testcase_55	AC	805 ms 90,720 KB
testcase_56	AC	1,751 ms 156,800 KB
testcase_57	AC	2,250 ms 186,036 KB
testcase_58	AC	546 ms 69,436 KB
testcase_59	AC	1,972 ms 167,336 KB
testcase_60	AC	2,105 ms 172,140 KB
testcase_61	AC	613 ms 72,064 KB
testcase_62	AC	1,366 ms 130,176 KB
testcase_63	AC	661 ms 70,016 KB
testcase_64	AC	863 ms 87,168 KB
testcase_65	AC	991 ms 94,272 KB
testcase_66	AC	696 ms 79,840 KB
testcase_67	AC	1,047 ms 108,160 KB
testcase_68	AC	2,431 ms 196,148 KB
testcase_69	AC	926 ms 98,800 KB
testcase_70	AC	2,288 ms 189,952 KB
testcase_71	AC	1,543 ms 136,704 KB
testcase_72	AC	2,228 ms 184,704 KB
testcase_73	AC	1,605 ms 143,348 KB
testcase_74	AC	1,127 ms 107,884 KB
testcase_75	AC	1,577 ms 140,672 KB
testcase_76	AC	1,483 ms 132,184 KB
testcase_77	AC	1,309 ms 123,264 KB
testcase_78	AC	1,727 ms 148,224 KB
testcase_79	AC	2,333 ms 188,520 KB
testcase_80	AC	2,437 ms 196,224 KB
testcase_81	AC	1,282 ms 118,144 KB
testcase_82	AC	1,493 ms 129,152 KB
testcase_83	AC	2,254 ms 183,548 KB
testcase_84	AC	1,523 ms 134,760 KB
testcase_85	AC	2,236 ms 186,112 KB
testcase_86	AC	1,488 ms 137,780 KB
testcase_87	AC	1,939 ms 166,912 KB
testcase_88	AC	1,253 ms 116,924 KB
testcase_89	AC	2,072 ms 174,080 KB
testcase_90	AC	2,572 ms 207,432 KB
testcase_91	AC	2,436 ms 207,456 KB
testcase_92	AC	2,517 ms 207,368 KB
testcase_93	AC	2,533 ms 207,448 KB
testcase_94	AC	2,544 ms 207,488 KB
testcase_95	AC	2,618 ms 207,488 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

結果

テストケース

ソースコード