ABC162 E - Sum of gcd of Tuples (Hard)
April 12, 2020
問題
考えたこと
数列のGCDの値が、1からKまでそれぞれいくつあるかを調べて
それらの合計値を取ればよさそう
1からKまで調べるのでO(K)かかるので、GCDの結果がある値になるときの数列の数を求めるのはlogNとか定数倍じゃないと間に合わなさそう..
GCDの結果がi(1~K)になるときの数列の数 の求め方
条件を考えてみる
- ある数列のGCDの値が
Xになるには、最低でも数列内のどの数もX以上じゃないといけないはず - ある数列のGCDの値が
Xになるには、数列内のどの数もXの倍数になっていないといけない
これらの条件から、GCDの結果がXになるときの数列の数 は次のような式で求めれそう
pow(K/X, N)
Kが数列内の数の最大値, Nが数列の長さXの倍数がX~Kまででいいくつあるかは、K/Xで求めれる, あとはこの組み合わせなので、数列の長さで冪乗をとってあげれば良い
重複の考慮
上記だと重複が発生する, 例えば K=2, N=3の条件が与えられたとき、GCD=1になる数を求めると
pow(2/1, 3) == 8ですが、実際は{2,2,2}という数列のGCDが2になるため、これを引いた7が正しい数になります。
このように重複が発生するため、それを考慮して計算しないといけません。
具体的には大きい値から決めていって、ある値をみる時に、その倍数がK以下であれば、すでに決まっている数を引いてあげるという感じです。
例えば、K=100, N=100でX=10の数を求めるときは、pow(100/10, 100)をした後に, pow(100/(10*2), 100), pow(100/(10*3), 100…pow(100/(10*10), 100)の数を減らしてあげれば良いです。
// GCDの結果がXになるときの数列の数を管理する配列
vector<ll> count(k+5, 0);
// 大きい方から確定させていく
for(ll i=k; i > 0; i--) {
// iの倍数がいくつあるかを求める
ll num = k/i;
// GCDの結果がiになるときの数列の数(重複を考慮しない)
ll tmpCount = modpow(num, n, modnum);
count[i] = tmpCount;
// iの倍数がk以下であれば、すでに確定している分を引いていく
ll ii = i*2;
while(ii <= k) {
count[i] -= count[ii];
ii += i;
}
}
このような感じで求めてあげて、最後にSUM(count[i]*i)みたいな感じで合計をとってあげればおkです。
前処理の計算量について
上記で書いたプログラムを簡略化すると,以下のようになる
for(ll i=k; i > 0; i--) {
ll ii = i*2;
while(ii <= k) {
ii += i;
}
}
これパッと見計算量がO(N^2)になりそうでは？と思えるが実際はN=10^5とした場合, O(10^6)くらいになる
確認してみる
上のプログラムを数式で表すと以下のようになる
i=1の時はwhileループの中を(K/1) - 1回i=2の時はwhileループの中を(K/2) - 1回
…i=Kの時はwhileループの中を(K/K) - 1回
と回るので
これがいくつになるかプログラムで確認すると
おおよそ10^6なのでこの前処理は十分に間に合う
提出したコード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
using Graph = vector<vector<int>>;
using P = pair<int, int>;
using Tuple = tuple<int, int, int>;
ll modnum = 1e9+7;
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
int main() {
ll n,k; cin >> n >> k;
ll ans = 0;
vector<ll> count(k+10, 0);
for(ll i=k; i > 0; i--) {
ll num = k/i;
ll tmp = modpow(num, n, modnum);
count[i] = tmp;
ll ii = i*2;
while(ii <= k) {
count[i] -= count[ii];
ii += i;
}
}
EFOR(i,1, k) {
ans += i*count[i]%modnum;
ans %= modnum;
}
cout << ans << endl;
return 0;
}