結果

問題 No.368 LCM of K-products
ユーザー kongarishisyamo
提出日時 2016-04-30 00:16:31
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,449 bytes
コンパイル時間 492 ms
コンパイル使用メモリ 64,172 KB
実行使用メモリ 41,552 KB
最終ジャッジ日時 2024-10-04 23:25:02
合計ジャッジ時間 7,123 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

#define mod (int)(pow(10.0,9)+7)

long long pn;
long long sk[1000];
long long p[4000];
long long hurui[40000];
long long a[1000];
long long ap[1000][4000];
long long sp[4000]={0};
long long sp2[4000];
bool f=false;
long long N,K;

void search(long long i,long long k){
	if(k==K){
		for(long long j=0;j<pn;j++){
			sp2[j]=0;
			for(long long q=0;q<K;q++){
				sp2[j]+=ap[sk[q]][j];
			}
			sp[j]=max(sp2[j],sp[j]);
		}
		return;
	}
	for(long long j=i;j<N;j++){
		sk[k]=j;
		search(j+1,k+1);
	}
}

long long strong_pow(long long n,long long k){
	n%=mod;
	if(k==0) return 1%mod;
	else if(k%2==0){
		long long num=strong_pow(n,k/2)%mod;
		return num*num%mod;
	}
	else{
		long long num=strong_pow(n,k-1)%mod;
		return num*n%mod;
	}
}

int main(){

	for(long long i=0;i<40000;i++) hurui[i]=0;

	for(long long i=2;i<=sqrt(pow(10.0,9));i++){
		if(hurui[i]==0){
			for(long long j=i;j<=sqrt(pow(10.0,9));j+=i){
				hurui[j]=1;
			}
			p[pn]=i;
			pn++;
		}
	}

	cin>>N>>K;
	for(long long i=0;i<N;i++){
		cin>>a[i];
	}
	for(long long i=0;i<N;i++){
		long long tmp=a[i];
		for(long long j=0;j<pn;j++){
			long long c=0;
			while(tmp!=0&&tmp%p[j]==0){
				tmp/=p[j];
				c++;
			}
			ap[i][j]=c;
		}
	}

	search(0,0);

	long long ans=1,tmp1;
	for(long long i=0;i<pn;i++){
		tmp1=strong_pow(p[i],sp[i]);
		tmp1%=mod;
		ans*=tmp1;
		ans%=mod;
		cout<<ans<<endl;
	}

	cout<<ans<<endl;
}
0