結果

問題 No.377 背景パターン
ユーザー cielciel
提出日時 2016-06-27 22:02:53
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 257 ms / 5,000 ms
コード長 1,469 bytes
コンパイル時間 1,159 ms
コンパイル使用メモリ 77,184 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 23:27:02
合計ジャッジ時間 2,205 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
5,248 KB
testcase_01 AC 5 ms
5,248 KB
testcase_02 AC 5 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 5 ms
5,248 KB
testcase_05 AC 5 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 5 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 5 ms
5,248 KB
testcase_10 AC 5 ms
5,248 KB
testcase_11 AC 5 ms
5,248 KB
testcase_12 AC 5 ms
5,248 KB
testcase_13 AC 6 ms
5,248 KB
testcase_14 AC 6 ms
5,248 KB
testcase_15 AC 5 ms
5,248 KB
testcase_16 AC 257 ms
5,248 KB
testcase_17 AC 241 ms
5,248 KB
testcase_18 AC 5 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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(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);
}
0