ABC162-E Sum of gcd of Tuples (Hard)

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2");
            //9
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 200");
            //10813692
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100000 100000");
            //742202979
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long N = wkArr[0];
        long K = wkArr[1];

        // GCDがXの倍数な数列の個数[引数X]なDict
        var CntDict = new Dictionary<long, long>();

        // 数列の各値が1からKなので、数列のGCDはN以下である
        // このGCDを降順に全探索する
        for (long I = K; 1 <= I; I--) {
            long UseNumCnt = K / I;

            // 数列の個数は、重複順列の個数
            long PatternCnt = DeriveModPow(UseNumCnt, N, Hou);

            for (long J = I * 2; J <= K; J += I) {
                PatternCnt -= CntDict[J];
                if (PatternCnt < 0) PatternCnt += Hou;
            }
            CntDict[I] = PatternCnt;
        }

        long Answer = 0;
        foreach (var EachPair in CntDict) {
            Answer += EachPair.Key * EachPair.Value;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }

    //繰り返し2乗法で、(NのP乗) Mod Mを求める
    static long DeriveModPow(long pN, long pP, long pM)
    {
        long CurrJyousuu = pN % pM;
        long CurrShisuu = 1;
        long WillReturn = 1;

        while (true) {
            //対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = (WillReturn * CurrJyousuu) % pM;
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
        }
    }
}

解説

GCDが1の数列が何通りあるか？
GCDが2の数列が何通りあるか？
GCDが3の数列が何通りあるか？
GCDが4の数列が何通りあるか？
GCDが5の数列が何通りあるか？
・・・
GCDがKの数列が何通りあるか？
が分かれば、解が分かります。

9以下の要素のみで、GCDが3の倍数になる数列(要素数は3)は、例えば、
3 3 3
3 6 9
6 6 6
9 9 9
などが考えられます。

6以下の要素のみで、GCDが6の倍数になる数列(要素数は3)は、例えば、
6 6 6
6 9 9
9 9 9
などが考えられます。

あとは、GCDの降順に考えれば解けます。