結果
問題 | No.1532 Different Products |
ユーザー | tada721 |
提出日時 | 2021-06-04 22:44:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,114 ms / 4,000 ms |
コード長 | 6,107 bytes |
コンパイル時間 | 1,630 ms |
コンパイル使用メモリ | 110,480 KB |
実行使用メモリ | 340,224 KB |
最終ジャッジ日時 | 2024-11-20 05:03:29 |
合計ジャッジ時間 | 41,207 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 191 ms
60,544 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 5 ms
5,248 KB |
testcase_08 | AC | 16 ms
6,912 KB |
testcase_09 | AC | 140 ms
37,760 KB |
testcase_10 | AC | 284 ms
83,584 KB |
testcase_11 | AC | 235 ms
69,376 KB |
testcase_12 | AC | 598 ms
174,848 KB |
testcase_13 | AC | 496 ms
132,608 KB |
testcase_14 | AC | 886 ms
279,552 KB |
testcase_15 | AC | 232 ms
48,896 KB |
testcase_16 | AC | 190 ms
66,304 KB |
testcase_17 | AC | 296 ms
81,408 KB |
testcase_18 | AC | 301 ms
77,184 KB |
testcase_19 | AC | 590 ms
169,728 KB |
testcase_20 | AC | 915 ms
284,160 KB |
testcase_21 | AC | 274 ms
94,080 KB |
testcase_22 | AC | 445 ms
121,088 KB |
testcase_23 | AC | 399 ms
99,072 KB |
testcase_24 | AC | 858 ms
262,272 KB |
testcase_25 | AC | 489 ms
149,248 KB |
testcase_26 | AC | 82 ms
26,240 KB |
testcase_27 | AC | 377 ms
125,440 KB |
testcase_28 | AC | 313 ms
101,120 KB |
testcase_29 | AC | 214 ms
76,672 KB |
testcase_30 | AC | 494 ms
165,888 KB |
testcase_31 | AC | 517 ms
169,856 KB |
testcase_32 | AC | 590 ms
196,992 KB |
testcase_33 | AC | 465 ms
152,448 KB |
testcase_34 | AC | 775 ms
244,736 KB |
testcase_35 | AC | 602 ms
195,968 KB |
testcase_36 | AC | 744 ms
237,184 KB |
testcase_37 | AC | 102 ms
40,704 KB |
testcase_38 | AC | 817 ms
254,336 KB |
testcase_39 | AC | 718 ms
226,432 KB |
testcase_40 | AC | 736 ms
231,296 KB |
testcase_41 | AC | 1,086 ms
330,112 KB |
testcase_42 | AC | 931 ms
292,992 KB |
testcase_43 | AC | 1,003 ms
306,688 KB |
testcase_44 | AC | 1,097 ms
334,336 KB |
testcase_45 | AC | 1,095 ms
335,360 KB |
testcase_46 | AC | 1,027 ms
325,120 KB |
testcase_47 | AC | 1,079 ms
338,688 KB |
testcase_48 | AC | 1,093 ms
334,848 KB |
testcase_49 | AC | 1,061 ms
336,640 KB |
testcase_50 | AC | 1,092 ms
334,208 KB |
testcase_51 | AC | 1,106 ms
337,792 KB |
testcase_52 | AC | 1,088 ms
331,264 KB |
testcase_53 | AC | 1,108 ms
339,072 KB |
testcase_54 | AC | 1,066 ms
331,392 KB |
testcase_55 | AC | 1,069 ms
336,128 KB |
testcase_56 | AC | 1,054 ms
324,736 KB |
testcase_57 | AC | 1,071 ms
327,296 KB |
testcase_58 | AC | 1,093 ms
333,312 KB |
testcase_59 | AC | 1,024 ms
314,496 KB |
testcase_60 | AC | 1,114 ms
340,224 KB |
testcase_61 | AC | 2 ms
5,248 KB |
testcase_62 | AC | 2 ms
5,248 KB |
testcase_63 | AC | 1,103 ms
336,000 KB |
コンパイルメッセージ
main.cpp: In function 'long long int keta(long long int)': main.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type] 41 | } | ^ main.cpp: In function 'long long int gcd(long long int, long long int)': main.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type] 55 | } | ^ main.cpp: In function 'long long int lcm(long long int, long long int)': main.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type] 68 | } | ^
ソースコード
#include<iostream>#include<algorithm>#include<cmath>#include<map>#include<stdio.h>#include<vector>#include<queue>#include<math.h>#include<deque>#include<set>#include<tuple>#include<string>using namespace std;#define ll long long#define int long long#define rep(s,i,n) for(int i=s;i<n;i++)#define c(n) cout<<n<<endl;#define ic(n) int n;cin>>n;#define sc(s) string s;cin>>s;#define mod 1000000007#define inf 2000000000000000007#define f first#define s second#define mini(c,a,b) *min_element(c+a,c+b)#define maxi(c,a,b) *max_element(c+a,c+b)#define pi 3.141592653589793238462643383279#define e_ 2.718281828459045235360287471352#define P pair<int,int>#define upp(a,n,x) upper_bound(a,a+n,x)-a;#define low(a,n,x) lower_bound(a,a+n,x)-a;#define UF UnionFind#define pb push_back//printf("%.12Lf\n",);int keta(int x) {rep(0, i, 30) {if (x < 10) {return i + 1;}x = x / 10;}}int gcd(int x, int y) {if (x == 0 || y == 0)return x + y;int aa = x, bb = y;rep(0, i, 1000) {aa = aa % bb;if (aa == 0) {return bb;}bb = bb % aa;if (bb == 0) {return aa;}}}int lcm(int x, int y) {int aa = x, bb = y;rep(0, i, 1000) {aa = aa % bb;if (aa == 0) {return x / bb * y;}bb = bb % aa;if (bb == 0) {return x / aa * y;}}}bool prime(int x) {if (x == 1)return false;rep(2, i, sqrt(x) + 1) {if (x % i == 0 && x != i) {return false;}}return true;}int max(int a, int b) {if (a >= b)return a;else return b;}string maxst(string s, string t) {int n = s.size();int m = t.size();if (n > m)return s;else if (n < m)return t;else {rep(0, i, n) {if (s[i] > t[i])return s;if (s[i] < t[i])return t;}return s;}}int min(int a, int b) {if (a >= b)return b;else return a;}int yakuwa(int n) {int sum = 0;rep(1, i, sqrt(n + 1)) {if (n % i == 0)sum += i + n / i;if (i * i == n)sum -= i;}return sum;}int poow(int n,int m){int pro=1;int nn=n;while(m){if(m%2==1)pro=pro*nn%mod;m=m/2;nn=nn*nn%mod;}return pro;}int poow2(int n,int m,int modulo){int pro=1;int nn=n;while(m){if(m%2==1)pro=pro*nn%modulo;m=m/2;nn=nn*nn%modulo;}return pro;}int inv(int n,int m){int t=poow(m,mod-2)%mod;return n*t%mod;}int com(int n,int m){if(n<m)return 0;int bunsi=1,bunbo=1;for(int i=n-m+1;i<=n;i++)bunsi=bunsi*i%mod;for(int i=1;i<=m;i++)bunbo=bunbo*i%mod;return inv(bunsi,bunbo);}int minpow(int x, int y) {int sum = 1;rep(0, i, y)sum *= x;return sum;}int ketawa(int x, int sinsuu) {int sum = 0;rep(0, i, 100)sum += (x % poow(sinsuu, i + 1)) / (poow(sinsuu, i));return sum;}int sankaku(int a) {return a * (a + 1) / 2;}int sames(int a[1111111], int n) {int ans = 0;rep(0, i, n) {if (a[i] == a[i + 1]) {int j = i;while (a[j + 1] == a[i] && j <= n - 2)j++;ans += sankaku(j - i);i = j;}}return ans;}struct UnionFind {vector<int> par;UnionFind(int n):par(n){rep(0,i,n)par[i]=i;}int root(int x){if (par[x]==x)return x;return par[x]=root(par[x]);}void unite(int x,int y){int rx=root(x);int ry=root(y);if (rx==ry) return;par[rx]=ry;}bool same(int x,int y){int rx=root(x);int ry=root(y);return rx==ry;}};int dijkstraa[514514];void dijkstra(int n,int m,int c[75000001],int d[75000001],int l[75000001],int siten,bool mukou){vector<P> e[514514];rep(0,i,m){e[c[i]].pb(P{l[i],d[i]});if(mukou)e[d[i]].pb(P{l[i],c[i]});}rep(0,i,n)dijkstraa[i]=inf;dijkstraa[siten]=0;priority_queue<P,vector<P>,greater<P>>pp;pp.push(P{0,siten});while(!pp.empty()){P t=pp.top();pp.pop();if(t.first!=dijkstraa[t.second])continue;rep(0,i,e[t.s].size()){P g=e[t.s][i];if(dijkstraa[g.second]>t.first+g.first){dijkstraa[g.second]=t.first+g.first;pp.push(P{dijkstraa[g.second],g.second});}}}}int dijkstra2(int shuten){return dijkstraa[shuten];}vector<int> toposo(vector<vector<int>> G,vector<int> indegree,int n){vector<int> sorted_vertices;queue<int> que;rep(0,i,n)if(!indegree[i])que.push(i);while(!que.empty()){int v=que.front();que.pop();rep(0,i,G[v].size()){int u=G[v][i];indegree[u]-=1;if(!indegree[u])que.push(u);}sorted_vertices.pb(v);}return sorted_vertices;}struct segtree{vector<int> dat;int n;segtree(int n_):n(),dat(n_*4,inf){int x=1;while(n_>=x)x*=2;n=x;}void update(int i,int x){i+=n-1;dat[i]=x;while(i>0){i=(i-1)/2;dat[i]=min(dat[i*2+1],dat[i*2+2]);}}int query(int a,int b){return query_sub(a,b,0,0,n);}int query_sub(int a,int b,int k,int l,int r){if(r<=a||b<=l)return inf;else if(a<=l&&r<=b)return dat[k];else{int vl=query_sub(a,b,k*2+1,l,(l+r)/2);int vr=query_sub(a,b,k*2+2,(l+r)/2,r);return min(vl,vr);}}int rightest(int a,int b,int x){return rightest_sub(a,b,x,0,0,n);}int rightest_sub(int a,int b,int x,int k,int l,int r){if(dat[k]>x||r<=a||b<=l)return a-1;else if(k>=n-1)return k-(n-1);else{int vr=rightest_sub(a,b,x,2*k+2,(l+r)/2,r);if(vr!=a-1)return vr;else return rightest_sub(a,b,x,2*k+1,l,(l+r)/2);}}int leftest(int a,int b,int x){return leftest_sub(a,b,x,0,0,n);}int leftest_sub(int a,int b,int x,int k,int l,int r){if(dat[k]>x||r<=a||b<=l)return b;else if(k>=n-1)return k-(n-1);else{int vl=leftest_sub(a,b,x,2*k+1,l,(l+r)/2);if(vl!=b)return vl;else return leftest_sub(a,b,x,2*k+2,(l+r)/2,r);}}};int dp[250][214514];//i番目までみてjまで掛けられるint a[214514];set<int> s;map<int,int> m;signed main(){ic(n) ic(k)rep(1,i,sqrt(k)+100)if(k/i)s.insert(k/i);rep(1,i,sqrt(k)+100)if((k/i)-k/(i+1)>0)s.insert(i);int t=s.size();int cnt=0;auto itr=s.begin();while(itr!=s.end()){a[cnt]=*itr;m[*itr]=cnt;itr++;cnt++;}dp[0][m[k]]=1;rep(1,i,n+1){rep(0,j,t){dp[i][j]+=dp[i-1][j];if(a[j]>=i){if(a[j]/i<sqrt(k))dp[i][a[j]/i-1]+=dp[i-1][j];else dp[i][m[a[j]/i]]+=dp[i-1][j];}}}int ans=0;rep(0,j,t)ans+=dp[n][j];c(ans-1)}