結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2020-03-13 12:26:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 993 bytes |
コンパイル時間 | 2,243 ms |
コンパイル使用メモリ | 198,780 KB |
最終ジャッジ日時 | 2025-01-09 06:37:23 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include<bits/stdc++.h> #define endl enjoy_codeforces using lint=long long; int main(){ std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false); lint n,k;std::cin>>n>>k; std::vector<lint>sieve(n,0); for(lint p=1;p<n;p++){ for(lint i=p;i<n;i+=p){ sieve.at(i)++; } } std::vector<lint>common(n,0); auto div=[&,n]()mutable{ std::vector<std::pair<lint,lint>>div; for(lint p=2;p*p<=n;p++){ if(n%p!=0)continue; lint i=0;for(;n%p==0;i++)n/=p; div.emplace_back(p,i); } if(n!=1)div.emplace_back(n,1); return div; }(); for(auto[p,m]:div){ for(lint q=p;m--;q*=p){ for(lint i=q;i<n;i+=q){ common.at(i)++; } } } lint ans=0,max=0; for(lint i=n-1;i>=1;i--){ if(k<=common.at(i)&&max<=sieve.at(i)){ ans=i; max=sieve.at(i); } } std::cout<<ans<<'\n'; }