結果

問題 No.847 Divisors of Power
コンテスト
ユーザー zunda1st
提出日時 2019-03-28 12:47:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,756 bytes
コンパイル時間 999 ms
コンパイル使用メモリ 98,308 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-06 20:58:18
合計ジャッジ時間 2,020 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<tuple>
#include<stdio.h>
#include<math.h>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Q;
typedef pair<Q,ll> R;
ll longinf=1ll<<60;
int inf=1<<29;
//mleしなければぜんぶllでかく。

vector<pair<ll,ll>> primeFactorDecomp(ll n){
	  vector<pair<ll,ll>> ret;
	  ll m=n;
	  for(ll i=2;i*i<=m;i++){
			if(n%i!=0) continue;
			ll cnt=0;
			while(n%i==0){
				  cnt++;
				  n/=i;
			}
			ret.push_back({i,cnt});
	  }
	  if(n>1){
			ret.push_back({n,1});
	  }
	  return ret;
}
ll m;
ll hukugen(vector<P>& p){
	ll ret=1;
	for(auto q:p){
		for(int i=1;i<=q.second;i++){
			ret*=q.first;
			if(ret >= 1e15) return 1e15+1;
		}
	}
	return ret;
}

int a[15];
ll expone[15];
int N;
bool nexta(int i){
	if(a[i]>=expone[i]){
		a[i]=0;
		nexta(i+1);
	}
	else{
		a[i]++;
		return true;
	}
	return true;
}

int main(){
	ll n,k;
	cin>>n>>k>>m;
	vector<P> bunkai=primeFactorDecomp(n);
	N=bunkai.size();
	for(int i=N;i<=N+1;i++){
		bunkai.push_back(make_pair(1e9+7, 2));
	}
	rep0(i,N+1) expone[i]= min(32ll, bunkai[i].second*k);
	rep0(i,N+1) a[i]=0;
	ll pos=1;
	ll ans=0;
	do{
		if(a[N]>0) break;
		/*rep0(i,N){
			cout<<a[i]<<" ";
		}
		cout<<endl;*/
		vector<P> posdec(N);
		rep0(i,N) posdec[i]={bunkai[i].first,a[i]};
		pos=hukugen(posdec);
		if(pos<=m&&pos>=0){
			ans++;
		}
		else{
			int i=0;
			while(a[i]==0){
				a[i]=expone[i];
				i++;
			}
			a[i]++;
		}
	}while(nexta(0));
	cout<<ans<<endl;

	return 0;
}
0