結果
問題 |
No.847 Divisors of Power
|
ユーザー |
|
提出日時 | 2021-12-24 04:54:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 1,182 bytes |
コンパイル時間 | 1,999 ms |
コンパイル使用メモリ | 205,356 KB |
最終ジャッジ日時 | 2025-01-27 06:10:30 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector <int> prime; bool isprime[31625]; void eratos(void) { memset(isprime,true,sizeof(isprime)); for(int i=2;i<31625;i++) { if(isprime[i]) { prime.push_back(i); for(int j=2*i;j<31625;j+=i) { isprime[j]=false; } } } } int main(void) { cin.tie(0); ios::sync_with_stdio(false); long long int n,k,m; set <long long int> S; vector <pair<long long int,long long int>> v; cin >> n >> k >> m; eratos(); long long int x = n; for(int j=0;j<prime.size();j++) { if(x==1 || x<prime[j]*prime[j]) { break; } long long int cnt = 0; while(1) { if(x%prime[j]!=0) { break; } cnt++; x/=prime[j]; } v.push_back(make_pair(prime[j],cnt*k)); } if(x>1) { v.push_back(make_pair(x,k)); } S.insert(1); for(int i=0;i<v.size();i++) { long long int p = v[i].first; long long int N = v[i].second; vector <long long int> temp; for(auto it : S) { long long int val = it; for(long long int j=0;j<N;j++) { val*=p; if(val > m) break; temp.push_back(val); } } for(auto it : temp) S.insert(it); } cout << S.size() << '\n'; return 0; }