結果

問題 No.847 Divisors of Power
コンテスト
ユーザー beet
提出日時 2019-07-05 21:36:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,271 bytes
コンパイル時間 2,257 ms
コンパイル使用メモリ 203,260 KB
最終ジャッジ日時 2025-01-07 05:54:23
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T>
map<T, Int> factorize(T x){
  map<T, Int> res;
  for(Int i=2;i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res[i]++;
    }
  }
  if(x!=1) res[x]++;
  return res;
}


template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}

//INSERT ABOVE HERE
signed main(){
  Int n,k,m;
  cin>>n>>k>>m;
  auto fc=factorize(n);
  for(auto &p:fc) p.second*=k;

  using P = pair<Int, Int>;
  vector<P> vp;
  for(auto &p:fc) vp.emplace_back(p);

  Int cnt=0;
  MFP([&](auto dfs,Int s,Int k)->void{
        if(s>m) return;
        if(k==(Int)vp.size()){
          cnt++;
          return;
        }
        for(Int i=0,t=1;i<=vp[k].second;i++){
          dfs(s*t,k+1);
          t*=vp[k].first;
          if(s*t>m) break;
        }
      })(1,0);

  cout<<cnt<<endl;
  return 0;
}
0