結果
問題 | No.1532 Different Products |
ユーザー | kotatsugame |
提出日時 | 2021-06-04 21:48:16 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,197 ms / 4,000 ms |
コード長 | 1,361 bytes |
コンパイル時間 | 877 ms |
コンパイル使用メモリ | 83,432 KB |
実行使用メモリ | 42,304 KB |
最終ジャッジ日時 | 2023-08-12 12:33:44 |
合計ジャッジ時間 | 98,426 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
4,388 KB |
testcase_01 | AC | 391 ms
21,376 KB |
testcase_02 | AC | 3 ms
4,384 KB |
testcase_03 | AC | 3 ms
4,392 KB |
testcase_04 | AC | 3 ms
4,400 KB |
testcase_05 | AC | 3 ms
4,444 KB |
testcase_06 | AC | 3 ms
4,544 KB |
testcase_07 | AC | 5 ms
4,684 KB |
testcase_08 | AC | 7 ms
5,252 KB |
testcase_09 | AC | 383 ms
20,628 KB |
testcase_10 | AC | 630 ms
28,884 KB |
testcase_11 | AC | 539 ms
27,248 KB |
testcase_12 | AC | 1,110 ms
35,768 KB |
testcase_13 | AC | 896 ms
40,160 KB |
testcase_14 | AC | 2,139 ms
37,764 KB |
testcase_15 | AC | 7 ms
5,308 KB |
testcase_16 | AC | 334 ms
18,504 KB |
testcase_17 | AC | 586 ms
30,980 KB |
testcase_18 | AC | 675 ms
34,888 KB |
testcase_19 | AC | 924 ms
37,136 KB |
testcase_20 | AC | 2,210 ms
39,620 KB |
testcase_21 | AC | 461 ms
21,692 KB |
testcase_22 | AC | 738 ms
34,980 KB |
testcase_23 | AC | 874 ms
39,300 KB |
testcase_24 | AC | 1,954 ms
38,452 KB |
testcase_25 | AC | 829 ms
31,384 KB |
testcase_26 | AC | 251 ms
16,768 KB |
testcase_27 | AC | 630 ms
24,256 KB |
testcase_28 | AC | 514 ms
25,196 KB |
testcase_29 | AC | 481 ms
17,524 KB |
testcase_30 | AC | 868 ms
27,688 KB |
testcase_31 | AC | 964 ms
28,324 KB |
testcase_32 | AC | 1,368 ms
30,532 KB |
testcase_33 | AC | 923 ms
27,036 KB |
testcase_34 | AC | 1,939 ms
35,968 KB |
testcase_35 | AC | 1,364 ms
30,724 KB |
testcase_36 | AC | 1,764 ms
34,008 KB |
testcase_37 | AC | 287 ms
12,092 KB |
testcase_38 | AC | 2,017 ms
36,092 KB |
testcase_39 | AC | 1,646 ms
33,808 KB |
testcase_40 | AC | 1,727 ms
34,344 KB |
testcase_41 | AC | 3,197 ms
41,940 KB |
testcase_42 | AC | 2,477 ms
39,184 KB |
testcase_43 | AC | 2,806 ms
40,412 KB |
testcase_44 | AC | 3,159 ms
41,800 KB |
testcase_45 | AC | 3,174 ms
42,040 KB |
testcase_46 | AC | 2,967 ms
41,144 KB |
testcase_47 | AC | 3,010 ms
42,136 KB |
testcase_48 | AC | 2,972 ms
41,792 KB |
testcase_49 | AC | 2,992 ms
41,924 KB |
testcase_50 | AC | 3,010 ms
41,760 KB |
testcase_51 | AC | 3,034 ms
42,024 KB |
testcase_52 | AC | 2,828 ms
41,596 KB |
testcase_53 | AC | 3,107 ms
42,156 KB |
testcase_54 | AC | 2,989 ms
41,612 KB |
testcase_55 | AC | 3,095 ms
41,940 KB |
testcase_56 | AC | 2,986 ms
41,072 KB |
testcase_57 | AC | 2,968 ms
41,324 KB |
testcase_58 | AC | 3,080 ms
41,744 KB |
testcase_59 | AC | 2,757 ms
40,284 KB |
testcase_60 | AC | 3,117 ms
42,304 KB |
testcase_61 | AC | 3 ms
4,524 KB |
testcase_62 | AC | 3 ms
4,384 KB |
testcase_63 | AC | 3,021 ms
41,876 KB |
ソースコード
#include<iostream> #include<vector> #include<map> using namespace std; int N; long K; long ans; int cnt[1<<17]; int cnt2[1<<17]; const int LIM=43; int main() { cin>>N>>K; map<long,int>mp; mp[1]=1; for(int i=2;i<=LIM&&i<=N;i++) { map<long,int>nxt; for(pair<long,int>p:mp) { long t=p.first; if(t*i>K) { if(t<1<<17)cnt[t]+=p.second; if(K/t<1<<17)cnt2[K/t]+=p.second; else cnt2[(1<<17)-1]+=p.second; } else { nxt[t]+=p.second; nxt[t*i]+=p.second; } } mp.swap(nxt); } for(pair<long,int>q:mp) { long p=q.first; if(p<1<<17)cnt[p]+=q.second; if(K/p<1<<17)cnt2[K/p]+=q.second; else cnt2[(1<<17)-1]+=q.second; } for(int i=1;i<1<<17;i++)cnt[i]+=cnt[i-1]; for(int i=(1<<17)-1;i--;)cnt2[i]+=cnt2[i+1]; if(N<=LIM) { cout<<(long)cnt2[0]*2-1<<endl; return 0; } ans=cnt2[1]; for(int i=LIM+1;i<=N;i++) { ans+=cnt2[i]; for(int j=i+1;j<=N;j++) { ans+=cnt2[i*j]; for(int k=j+1;k<=N;k++) { int t=i*j*k; if(t>K)break; if(t<1<<17)ans+=cnt2[t]; else ans+=cnt[K/t]; for(int l=k+1;l<=N;l++) { int u=t*l; if(u>K)break; if(u<1<<17)ans+=cnt2[u]; else ans+=cnt[K/u]; for(int m=l+1;m<=N;m++) { long v=(long)u*m; if(v>K)break; if(v<1<<17)ans+=cnt2[v]; else ans+=cnt[K/v]; } } } } } cout<<ans*2-1<<endl; }