#100170 (C++14) No.377 背景パターン

• 問題: No.377 背景パターン
• ユーザー: ciel
• 提出日時: 2016-06-27 22:03:06
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 267 ms / 5,000 ms
• コード長: 1,469 bytes
• コンパイル時間: 981 ms
• コンパイル使用メモリ: 84,884 KB
• 実行使用メモリ: 4,384 KB
• 最終ジャッジ日時: 2023-08-25 14:11:54
• 合計ジャッジ時間: 2,294 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	8 ms; 4,384 KB
testcase_01	AC	8 ms; 4,380 KB
testcase_02	AC	8 ms; 4,376 KB
testcase_03	AC	8 ms; 4,376 KB
testcase_04	AC	8 ms; 4,376 KB
testcase_05	AC	9 ms; 4,380 KB
testcase_06	AC	8 ms; 4,380 KB
testcase_07	AC	8 ms; 4,380 KB
testcase_08	AC	8 ms; 4,376 KB
testcase_09	AC	8 ms; 4,376 KB
testcase_10	AC	8 ms; 4,380 KB
testcase_11	AC	8 ms; 4,380 KB
testcase_12	AC	8 ms; 4,380 KB
testcase_13	AC	8 ms; 4,380 KB
testcase_14	AC	10 ms; 4,380 KB
testcase_15	AC	8 ms; 4,380 KB
testcase_16	AC	267 ms; 4,380 KB
testcase_17	AC	251 ms; 4,380 KB
testcase_18	AC	9 ms; 4,376 KB

ソースコード

#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(const 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);
}