精進記録

言語はc++です

E - Sum of gcd of Tuples (Hard) #AtCoder

atcoder.jp

問題概要

入力N、Kが与えられる。
1以上K以下の整数からなる長さNの数列Aについて、考えられる全てのAのgcd{A_1, A_2,...,A_N}の総和を求めさせる問題。

サンプル1

3 4

という入力であった場合(N=3、K=4)
数列は項数が3個で、各項は1or2or3or4となる。
例えば{1、1、2}や{2、3、1}や{4、4、3}が考えられる。
そして各数列に対して各項の最大公約数を求めたい。ということである。

まず考えうる全ての数列を列挙してみる。

1 1 1 
1 1 2
1 1 3
1 1 4
1 2 1
1 2 2
1 2 3
1 2 4
1 3 1
1 3 2
1 3 3
1 3 4
1 4 1
1 4 2
1 4 3 
1 4 4
2 1 1
2 1 2
2 1 3
2 1 4
2 2 1
2 2 2
2 2 3
2 2 4
2 3 1
2 3 2
2 3 3
2 3 4 
2 4 1
2 4 2
2 4 3
2 4 4
3 1 1
3 1 2
3 1 3
3 1 4
3 2 1
3 2 2
3 2 3
3 2 4
3 3 1
3 3 2
3 3 3
3 3 4
3 4 1
3 4 2
3 4 3
3 4 4
4 1 1
4 1 2
4 1 3
4 1 4
4 2 1
4 2 2
4 2 3
4 2 4
4 3 1
4 3 2
4 3 3
4 3 4
4 4 1
4 4 2
4 4 3 
4 4 4

そして各数列に対して各項の最大公約数を求めます。

1 1 1 -> 1
1 1 2 -> 1
1 1 3 -> 1
1 1 4 -> 1
1 2 1 -> 1
1 2 2 -> 1
1 2 3 -> 1
1 2 4 -> 1
1 3 1 -> 1
1 3 2 -> 1
1 3 3 -> 1
1 3 4 -> 1
1 4 1 -> 1
1 4 2 -> 1
1 4 3 -> 1
1 4 4 -> 1
2 1 1 -> 1
2 1 2 -> 1
2 1 3 -> 1
2 1 4 -> 1
2 2 1 -> 1
2 2 2 -> 2
2 2 3 -> 1
2 2 4 -> 2
2 3 1 -> 1
2 3 2 -> 1
2 3 3 -> 1
2 3 4 -> 1
2 4 1 -> 1
2 4 2 -> 2
2 4 3 -> 1
2 4 4 -> 2
3 1 1 -> 1
3 1 2 -> 1
3 1 3 -> 1
3 1 4 -> 1
3 2 1 -> 1
3 2 2 -> 1
3 2 3 -> 1
3 2 4 -> 1
3 3 1 -> 1
3 3 2 -> 1
3 3 3 -> 3
3 3 4 -> 1
3 4 1 -> 1
3 4 2 -> 1
3 4 3 -> 1
3 4 4 -> 1
4 1 1 -> 1
4 1 2 -> 1
4 1 3 -> 1
4 1 4 -> 1
4 2 1 -> 1
4 2 2 -> 2
4 2 3 -> 1
4 2 4 -> 2
4 3 1 -> 1
4 3 2 -> 1
4 3 3 -> 1
4 3 4 -> 1
4 4 1 -> 1
4 4 2 -> 2
4 4 3 -> 1
4 4 4 -> 4

これらの総和を取ります。

1 1 1 -> 1 sum = 1
1 1 2 -> 1 sum = 2
1 1 3 -> 1 sum = 3
1 1 4 -> 1 sum = 4
1 2 1 -> 1 sum = 5
1 2 2 -> 1 sum = 6
1 2 3 -> 1 sum = 7
1 2 4 -> 1 sum = 8
1 3 1 -> 1 sum = 9
1 3 2 -> 1 sum = 10
1 3 3 -> 1 sum = 11
1 3 4 -> 1 sum = 12
1 4 1 -> 1 sum = 13
1 4 2 -> 1 sum = 14
1 4 3 -> 1 sum = 15
1 4 4 -> 1 sum = 16
2 1 1 -> 1 sum = 17
2 1 2 -> 1 sum = 18
2 1 3 -> 1 sum = 19
2 1 4 -> 1 sum = 20
2 2 1 -> 1 sum = 21
2 2 2 -> 2 sum = 23
2 2 3 -> 1 sum = 24
2 2 4 -> 2 sum = 26
2 3 1 -> 1 sum = 27
2 3 2 -> 1 sum = 28
2 3 3 -> 1 sum = 29
2 3 4 -> 1 sum = 30
2 4 1 -> 1 sum = 31
2 4 2 -> 2 sum = 33
2 4 3 -> 1 sum = 34
2 4 4 -> 2 sum = 36
3 1 1 -> 1 sum = 37
3 1 2 -> 1 sum = 38
3 1 3 -> 1 sum = 39
3 1 4 -> 1 sum = 40
3 2 1 -> 1 sum = 41
3 2 2 -> 1 sum = 42
3 2 3 -> 1 sum = 43
3 2 4 -> 1 sum = 44
3 3 1 -> 1 sum = 45
3 3 2 -> 1 sum = 46
3 3 3 -> 3 sum = 49
3 3 4 -> 1 sum = 50
3 4 1 -> 1 sum = 51
3 4 2 -> 1 sum = 52
3 4 3 -> 1 sum = 53
3 4 4 -> 1 sum = 54
4 1 1 -> 1 sum = 55
4 1 2 -> 1 sum = 56
4 1 3 -> 1 sum = 57
4 1 4 -> 1 sum = 58
4 2 1 -> 1 sum = 59
4 2 2 -> 2 sum = 61
4 2 3 -> 1 sum = 62
4 2 4 -> 2 sum = 64
4 3 1 -> 1 sum = 65
4 3 2 -> 1 sum = 66
4 3 3 -> 1 sum = 67
4 3 4 -> 1 sum = 68
4 4 1 -> 1 sum = 69
4 4 2 -> 2 sum = 71
4 4 3 -> 1 sum = 72
4 4 4 -> 4 sum = 76
ans = 76

答えは76と求まりました。

ではここで少し観察として、最大公約数が2か4となっているものだけを抽出してみたいと思います。

2 2 2 -> 2
2 2 4 -> 2
2 4 2 -> 2
2 4 4 -> 2
4 2 2 -> 2
4 2 4 -> 2
4 4 2 -> 2
4 4 4 -> 4

当たり前ですが、各項は2の倍数のみで構成されています。
はい。ここで取り出したものは「最大公約数が2の倍数であるもの」たちです。
この「最大公約数が2の倍数であるもの」たちの個数は計算によって求められます。
前提として、各項は必ず2の倍数でないといけません。K(=4)以下で2の倍数となるものはK/2=4/2=2個です。3の倍数であるものを計算したいときはK/3=4/3=1個となってくれて、実装時にはint型でそのまま割り算してよいです。
項の候補が2通りしかないことが分かりましたので、構成されうる数列の数は2N=23=8個ということが分かります。
ここで「最大公約数が2の倍数」ではなく「最大公約数が2である」数列の個数を数える方法を考えます。
なぜなら、最大公約数がpである数列の個数が分かっているとその部分の総和は簡単に求められるようになるからです。
この部分が解説pdfで言っている

そこで、1≦X≦Kに対して「gcd(A1,...,AN)=Xとなる数列{Ai}がいくつあるか?」という問題を考えます。これが解ければ元の問題にも答えることが出来ます。

の部分にあたります。
では、「最大公約数が2である」数列の個数を考えましょう。
先の計算では「最大公約数が2の倍数」である数列の個数を簡単に求めることが出来ました。しかしこれは2の他にも最大公約数が4である数列も含まれています。
「2の倍数」を数えることが出来たので当然「4の倍数」の数も数えることができるはずです。
(K/4)N=(4/4)3=1より1個です。上でいう、{4,4,4}がそれに該当しますね。
この数を「2の倍数」から引くことで無事「最大公約数が2である」数列の個数が求まりました。

実装

まず、「最大公約数がiの倍数となる」数列の個数を数えます。
大きな数での計算になるので繰り返し二乗法を利用します。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int N,K;
long ans;

//繰り返し二乗法
//a^n mod m を返す
long power(long a, long n, long m)
{
        long ret = 1;
        for (; n > 0; n >>= 1, a = a * a % m)
        {
                if (n % 2 == 1)
                {
                        ret = ret * a % m;
                }
        }
        return ret;
}

main()
{
        cin>>N>>K;
        for(int i=1;i<=K;i++)
        {
                long cnt=(power(K/i,N,mod)%mod+mod)%mod;

main関数の中のfor文に注目してください。int i=1;i<=K;i++と小さい数から始めています。
しかしこれでは、例えば「2の倍数」の数を求めたとしても「4、6、8、、、の倍数」の個数が分かっていないので引き算のしようがなく「2のみ」の個数が求められません。
ここで解決策としてループを小さい数からではなく大きい数つまりi=Kから始めます。

先のサンプルの場合、
i=4から始めることとなります。
「最大公約数が4の倍数」となる個数は1個と簡単に計算できました。この時、引き算する分はあるでしょうかありません。なぜなら一番大きい数字だからです。4の倍数である8や12はここでは登場しません。つまりここで計算した「最大公約数が4の倍数」である個数はすなわち「最大公約数が4である」数列の個数であると言えるのです。引き算せずにこのままansに足してあげてよいです。
ですが、この4の約数である2は引き算する必要がありました。「4の倍数」分です。
なので、このi=4の時点でその約数である2に引き算する分を配列として残して置きましょう。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int N,K;
long ans;
vector<long> X(100100); //引き算する分を保存する配列

//繰り返し二乗法
//a^n mod m を返す
long power(long a, long n, long m)
{
        long ret = 1;
        for (; n > 0; n >>= 1, a = a * a % m)
        {
                if (n % 2 == 1)
                {
                        ret = ret * a % m;
                }
        }
        return ret;
}


//nの約数をpush_backしたvectorを返す
vector<long> divisor(long n)
{
        vector<long> res;
        for(long i = 1; i * i <= n; i++)
        {
                if(n % i == 0)
                {
                        res.push_back(i);
                        if(i * i != n) res.push_back(n / i);
                }
        }
        sort(res.begin(), res.begin());
        return res;
}

main()
{
        cin>>N>>K;
        for(int i=K;i>0;i--) //Kからの降順にした
        {
                //X[i]が引き算する分
                //i=Kでは当然X[i]=0
                long cnt=((power(K/i,N,mod)-X[i])%mod+mod)%mod; 
                //最大公約数がiである数列の個数がcnt個と分かった
                ans=(ans+i*cnt+mod)%mod;

                vector<long> d=divisor(i);
                //約数の子たちのために引き算する分を教えてあげている
                for(auto &it : d)X[it]=(X[it]+cnt+mod)%mod; 
        }
        cout<<ans<<endl;
}

配列としてvector X(100100)を置きます。
ここに例えばi=4の時にはその個数を約数2の部分に入れるということをします。

X[2]+=cnt

これが i-- されていってi=2となったときに引き算されるというわけです。

コード自体はとりあえずこれにて完成です。
ここまでお読み頂いた方ありがとうございました。