Submission #366341
Source Code Expand
#include<iostream> #include<fstream> #include<sstream> #include<string> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<stack> #include<queue> #include<set> #include<map> #include<vector> #include<list> #include<algorithm> #include<utility> #include<complex> #include<functional> using namespace std; #define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++) #define rE(i,b) reE(i,0,b) #define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++) #define rT(i,b) reT(i,0,b) #define rep(i,a,b) reE(i,a,b); #define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--) #define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i)) #define rti(i,b) for(auto (i)=(b).rbegin();(i)!=(b).rend();++(i)) #define LL long long #define all(b) (b).begin(),(b).end() #define input_init stringstream ss; string strtoken, token; istringstream is #define input_line getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit) #define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num #define dir(xx,yy,x,y,i) (xx)=(x)+dir[(i)],(yy)=(y)+dir[(i)+1] typedef complex<double> P; typedef vector<P> Poly; const LL INF = 1 << 30; const double eps = 1e-8; const int dir[] = { 0, 1, 0, -1, 0 }; #define MOD 1000000007 //等差数列の和 inline LL sum(LL st, LL ed, LL d){ LL n = (ed - st) / d+1; return (n*(st + ed)) / 2; } inline vector<LL> divisor(LL N){ list<LL> res; LL i; for (i = 1ll; i*i < N; i++) if (N%i == 0){ res.push_back(i); res.push_back(N / i); } if (N%i==0)res.push_back(i); vector<LL> ans(all(res)); sort(all(ans),greater<LL>()); return ans; } int main(void){ LL N, K; cin >> N >> K; auto div = divisor(K); vector<LL> res(div.size()); rT(i, (int)div.size()){ res[i] = sum(div[i], div[i]*(N / div[i]),div[i]); rT(j, i)if (div[j] % div[i] == 0)res[i] -= res[j]; } LL ans = 0; rT(i, (int)div.size()){ LL X = K / div[i]; ans = (ans + (X*(res[i] % MOD)) % MOD) % MOD; } cout << ans << endl; return(0); }
Submission Info
Submission Time | |
---|---|
Task | D - LCM Rush |
User | btk15049 |
Language | C++11 (GCC 4.9.2) |
Score | 101 |
Code Size | 2101 Byte |
Status | AC |
Exec Time | 47 ms |
Memory | 932 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 5 / 5 | 10 / 10 | 85 / 85 | 1 / 1 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt |
Subtask1 | subtask0_sample_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt |
Subtask2 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt |
Subtask3 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask3_31.txt, subtask3_32.txt, subtask3_33.txt, subtask3_34.txt, subtask3_35.txt, subtask3_36.txt, subtask3_37.txt, subtask3_38.txt, subtask3_39.txt, subtask3_40.txt, subtask3_41.txt, subtask3_42.txt, subtask3_43.txt, subtask3_44.txt, subtask3_45.txt |
Subtask4 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask3_31.txt, subtask3_32.txt, subtask3_33.txt, subtask3_34.txt, subtask3_35.txt, subtask3_36.txt, subtask3_37.txt, subtask3_38.txt, subtask3_39.txt, subtask3_40.txt, subtask3_41.txt, subtask3_42.txt, subtask3_43.txt, subtask3_44.txt, subtask3_45.txt, subtask4_46.txt, subtask4_47.txt, subtask4_48.txt, subtask4_49.txt, subtask4_50.txt, subtask4_51.txt, subtask4_52.txt, subtask4_53.txt, subtask4_54.txt, subtask4_55.txt, subtask4_56.txt, subtask4_57.txt, subtask4_58.txt, subtask4_59.txt, subtask4_60.txt, subtask4_61.txt, subtask4_62.txt, subtask4_63.txt, subtask4_64.txt, subtask4_65.txt, subtask4_66.txt, subtask4_67.txt, subtask4_68.txt, subtask4_69.txt, subtask4_70.txt, subtask4_71.txt, subtask4_72.txt, subtask4_73.txt, subtask4_74.txt, subtask4_75.txt, subtask4_76.txt, subtask4_77.txt, subtask4_78.txt, subtask4_79.txt, subtask4_80.txt, subtask4_81.txt, subtask4_82.txt, subtask4_83.txt, subtask4_84.txt, subtask4_85.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 26 ms | 732 KB |
subtask0_sample_02.txt | AC | 25 ms | 800 KB |
subtask0_sample_03.txt | AC | 25 ms | 792 KB |
subtask0_sample_04.txt | AC | 24 ms | 800 KB |
subtask1_01.txt | AC | 23 ms | 928 KB |
subtask1_02.txt | AC | 25 ms | 764 KB |
subtask1_03.txt | AC | 22 ms | 924 KB |
subtask1_04.txt | AC | 22 ms | 800 KB |
subtask1_05.txt | AC | 22 ms | 928 KB |
subtask1_06.txt | AC | 23 ms | 928 KB |
subtask1_07.txt | AC | 25 ms | 764 KB |
subtask1_08.txt | AC | 22 ms | 928 KB |
subtask1_09.txt | AC | 23 ms | 796 KB |
subtask1_10.txt | AC | 22 ms | 796 KB |
subtask1_11.txt | AC | 22 ms | 800 KB |
subtask1_12.txt | AC | 24 ms | 796 KB |
subtask1_13.txt | AC | 23 ms | 928 KB |
subtask1_14.txt | AC | 22 ms | 928 KB |
subtask1_15.txt | AC | 25 ms | 792 KB |
subtask2_16.txt | AC | 25 ms | 796 KB |
subtask2_17.txt | AC | 25 ms | 920 KB |
subtask2_18.txt | AC | 23 ms | 744 KB |
subtask2_19.txt | AC | 22 ms | 800 KB |
subtask2_20.txt | AC | 22 ms | 804 KB |
subtask2_21.txt | AC | 22 ms | 928 KB |
subtask2_22.txt | AC | 27 ms | 800 KB |
subtask2_23.txt | AC | 23 ms | 804 KB |
subtask2_24.txt | AC | 25 ms | 928 KB |
subtask2_25.txt | AC | 24 ms | 804 KB |
subtask2_26.txt | AC | 25 ms | 736 KB |
subtask2_27.txt | AC | 23 ms | 928 KB |
subtask2_28.txt | AC | 23 ms | 920 KB |
subtask2_29.txt | AC | 25 ms | 800 KB |
subtask2_30.txt | AC | 24 ms | 920 KB |
subtask3_31.txt | AC | 23 ms | 808 KB |
subtask3_32.txt | AC | 24 ms | 840 KB |
subtask3_33.txt | AC | 23 ms | 928 KB |
subtask3_34.txt | AC | 24 ms | 924 KB |
subtask3_35.txt | AC | 25 ms | 924 KB |
subtask3_36.txt | AC | 24 ms | 804 KB |
subtask3_37.txt | AC | 24 ms | 932 KB |
subtask3_38.txt | AC | 22 ms | 924 KB |
subtask3_39.txt | AC | 23 ms | 796 KB |
subtask3_40.txt | AC | 25 ms | 796 KB |
subtask3_41.txt | AC | 24 ms | 792 KB |
subtask3_42.txt | AC | 25 ms | 920 KB |
subtask3_43.txt | AC | 24 ms | 928 KB |
subtask3_44.txt | AC | 24 ms | 676 KB |
subtask3_45.txt | AC | 23 ms | 920 KB |
subtask4_46.txt | AC | 26 ms | 732 KB |
subtask4_47.txt | AC | 23 ms | 928 KB |
subtask4_48.txt | AC | 45 ms | 924 KB |
subtask4_49.txt | AC | 43 ms | 928 KB |
subtask4_50.txt | AC | 45 ms | 796 KB |
subtask4_51.txt | AC | 42 ms | 924 KB |
subtask4_52.txt | AC | 47 ms | 776 KB |
subtask4_53.txt | AC | 45 ms | 800 KB |
subtask4_54.txt | AC | 37 ms | 808 KB |
subtask4_55.txt | AC | 36 ms | 928 KB |
subtask4_56.txt | AC | 37 ms | 928 KB |
subtask4_57.txt | AC | 36 ms | 812 KB |
subtask4_58.txt | AC | 38 ms | 800 KB |
subtask4_59.txt | AC | 35 ms | 800 KB |
subtask4_60.txt | AC | 25 ms | 796 KB |
subtask4_61.txt | AC | 26 ms | 804 KB |
subtask4_62.txt | AC | 24 ms | 928 KB |
subtask4_63.txt | AC | 23 ms | 928 KB |
subtask4_64.txt | AC | 38 ms | 804 KB |
subtask4_65.txt | AC | 40 ms | 924 KB |
subtask4_66.txt | AC | 41 ms | 920 KB |
subtask4_67.txt | AC | 38 ms | 800 KB |
subtask4_68.txt | AC | 30 ms | 800 KB |
subtask4_69.txt | AC | 30 ms | 924 KB |
subtask4_70.txt | AC | 24 ms | 928 KB |
subtask4_71.txt | AC | 24 ms | 924 KB |
subtask4_72.txt | AC | 24 ms | 800 KB |
subtask4_73.txt | AC | 26 ms | 772 KB |
subtask4_74.txt | AC | 24 ms | 792 KB |
subtask4_75.txt | AC | 25 ms | 924 KB |
subtask4_76.txt | AC | 26 ms | 720 KB |
subtask4_77.txt | AC | 24 ms | 932 KB |
subtask4_78.txt | AC | 24 ms | 796 KB |
subtask4_79.txt | AC | 25 ms | 800 KB |
subtask4_80.txt | AC | 24 ms | 928 KB |
subtask4_81.txt | AC | 23 ms | 924 KB |
subtask4_82.txt | AC | 24 ms | 932 KB |
subtask4_83.txt | AC | 25 ms | 920 KB |
subtask4_84.txt | AC | 26 ms | 796 KB |
subtask4_85.txt | AC | 26 ms | 732 KB |