結果
問題 | No.1383 Numbers of Product |
ユーザー |
|
提出日時 | 2021-02-07 22:09:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,827 ms / 2,000 ms |
コード長 | 953 bytes |
コンパイル時間 | 801 ms |
コンパイル使用メモリ | 86,196 KB |
実行使用メモリ | 130,944 KB |
最終ジャッジ日時 | 2024-11-22 23:20:45 |
合計ジャッジ時間 | 33,336 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 51 |
コンパイルメッセージ
main.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 37 | main() | ^~~~
ソースコード
#include<iostream>#include<cmath>#include<map>#include<vector>#include<set>using namespace std;long N,K,M;map<long,long>cnt;long count2(){long L=0,R=1e9;while(R-L>1){long mid=(L+R)/2;if(mid+K>N/mid)R=mid;else L=mid;}return L;}long A;bool isok(long T){__int128 V=(__int128)K*K+4*T;__int128 L=0,R=1;while(R*R<V)R*=2;while(R-L>1){long mid=(L+R)/2;if(mid*mid<V)L=mid;else R=mid;}if(R*R!=V)return false;if((R-K)%2!=0)return false;__int128 a=(R-K)/2;return a>=A;}main(){cin>>N>>K>>M;A=1;for(;;A++){if(A+K>N/A)break;long T=A;long U=A+K;int tm=0;while(U<=N/T){T*=U;U+=K;cnt[T]++;tm++;}if(tm==1){cnt[T]--;if(cnt[T]==0)cnt.erase(T);break;}}long one=count2()-A+1;long ans=0;for(pair<long,long>p:cnt){int now=p.second;if(isok(p.first)){one--;now++;}if(now==M)ans++;}cout<<ans+(M==1?one:0)<<endl;}