結果

問題 No.377 背景パターン
コンテスト
ユーザー vjudge1
提出日時 2026-09-18 07:36:51
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 484 ms / 5,000 ms
+ 369µs
コード長 1,785 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,494 ms
コンパイル使用メモリ 224,672 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-09-18 07:36:58
合計ジャッジ時間 4,072 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
const ll MOD = 1e9 + 7;
map<ll, ll>val;
ll phi(ll n)
{
	if(n == 1)
	{
		return 1;
	}
	if(val.count(n) == 1)
	{
		return val[n];
	}
	ll n1 = n;
	ll ans = n, i;
	for(i = 2; i * i <= n; i++)
	{
		if(n % i == 0)
		{
			while(n % i == 0)
			{
				n /= i;	
			}
			ans -= ans / i;
		}
	}
	if(n > 1)
	{
		ans -= ans / n;
	}
	val[n1] = ans;
	return ans;
}
ll mu(ll a, ll b)
{
	ll ans = 1;
	while(b > 0)
	{
		if(b % 2 == 1)
		{
			ans *= a;
			ans %= MOD;
		}
		b /= 2;
		a *= a;
		a %= MOD;
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t = 1;
	//cin >> t;
	while(t--)
	{
		ll n, m, k;
		cin >> n >> m >> k;
		vector<ll>div, div1;
		ll i;
		for(i = 1; i * i <= n; i++)
		{
			if(n % i == 0)
			{
				div.push_back(i);
				if(n / i != i)
				{
					div.push_back(n / i);
				}
			}
		}
		for(i = 1; i * i <= m; i++)
		{
			if(m % i == 0)
			{
				div1.push_back(i);
				if(m / i != i)
				{
					div1.push_back(m / i);
				}
			}
		}
		sort(div.begin(), div.end());
		sort(div1.begin(), div1.end());
		for(i = 0; i < div.size(); i++)
		{
			phi(n / div[i]);
		}
		for(i = 0; i < div1.size(); i++)
		{
			phi(m / div1[i]);
		}
		ll j, ans = 0;
		for(i = 0; i < div.size(); i++)
		{
			for(j = 0; j < div1.size(); j++)
			{
				ans += phi(n / div[i]) * phi(m / div1[j]) % MOD * mu(k, div[i] * div1[j] * __gcd(n / div[i], m / div1[j])) % MOD;
				ans %= MOD;
				//cout << div[i] << " " << div1[j] << " " << ans << endl;
			}
		}
		ans *= mu(n * m % MOD, MOD - 2);
		ans %= MOD;
		cout << ans << endl;
	}
	#ifndef ONLINE_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	#endif
	return 0;
}
// Author: tryharderforioi100
0