結果

問題 No.377 背景パターン
ユーザー ciel
提出日時 2016-06-05 16:36:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 339 ms / 5,000 ms
コード長 1,461 bytes
コンパイル時間 1,030 ms
コンパイル使用メモリ 78,120 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 03:49:08
合計ジャッジ時間 2,884 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::vector<std::pair<long long int, int> > prime_division(long long int)’:
main.cpp:21:15: warning: ignoring return value of ‘int fscanf(FILE*, const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   21 |         fscanf(p,"%lld:",&x);
      |         ~~~~~~^~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:45:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |         scanf("%lld%lld%lld",&H,&W,&K);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <string>
#include <vector>
#include <unordered_map>
#include <functional>
#include <cstdio>
using namespace std;
const int M=1000000007;
long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}
long long pow(long long x,long long y,long long m){
	long long z=1;
	for(;y;y/=2){
		if(y&1)z=z*x%m;
		x=x*x%m;
	}
	return z;
}
vector<pair<long long,int>> prime_division(long long n){
	unordered_map<long long,int>se;
	FILE *p=popen((string("factor ")+to_string(n)).c_str(),"r");
	long long x;
	fscanf(p,"%lld:",&x);
	for(;~fscanf(p,"%lld",&x);)se[x]++;
	pclose(p);
	vector<pair<long long,int>>v;
	v.insert(v.end(),se.begin(),se.end());
	return v;
}
void divisor_totient(vector<pair<long long,int>>a,int d,long long n,long long t,const function<void(long long&,long long&)>&blk){
	if(d==a.size()){
		blk(n,t);
	}else{
		for(int i=0;i<=a[d].second;i++){
			divisor_totient(
				a,d+1,
				n*pow(a[d].first,i,M),
				i==0 ? t : t*(a[d].first-1)*pow(a[d].first,i-1,M),
				blk
			);
		}
	}
}
int main(){
	unordered_map<long long,int>cache;
	long long H,W,K,r=0;
	scanf("%lld%lld%lld",&H,&W,&K);
	auto a=prime_division(H);
	auto b=prime_division(W);
	divisor_totient(a,0,1,1,[&](long long &a,long long &at){
		divisor_totient(b,0,1,1,[&](long long &b,long long &bt){
			long long key=W*H/a/b*gcd(a,b);
			if(cache.find(key)==cache.end())cache.emplace(key,pow(K,key,M));
			r=(r+at*bt%M*cache.at(key))%M;
		});
	});
	printf("%lld\n",r*pow(W*H%M,M-2,M)%M);
}
0