SRM613D1Med RandomGCD
こういうのは得意
問題概要(原文)
$low$ 以上 $high$ 以下の整数を $N$ 個並べた数列のGCDが $K$ となるような数列は何通りあるか？ MOD $10^9+7$ で求めよ．
考察
GCDが $K$ になるというのは全て $K$ の倍数ということなので， $K$ で割ったあまりが $0$ でないものは考えないようにすればよい．よって以降GCDは $1$ として考える．
あとは包除原理+DPをやるだけになる． ある整数 $k$ に着目しているとき，GCDが $k$ になるような通り数 $f(k)$ は $k$ の倍数であって，validなものの個数を $n$ として以下のように表せる．
\[ f(k) = pow(n,N) - \sum_{i=2}^{\infty} f(i \times k) \]
実際に見る必要性があるのは $high$ までである．また，見なくてはならない区間は連続かつ狭いので，ふるいっぽく見ていけばよい．
ステップ数は $10^{5} log 10^{5}$ 程度
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class RandomGCD
{
public int countTuples(int N, int K, int low, int high)
{
var xs = new List<int>();
for (int i = low; i <= high; i++)
{
if (i % K != 0) continue;
xs.Add(i / K);
}
if (xs.Count == 0) return 0;
ModInteger ans = 0;
var dp1 = new ModInteger[100050];
var dp2 = new ModInteger[xs.Count];
for (int i = xs.Count - 1; i >= 0; i--)
{
var x = xs[i];
if (x <= 100000) continue;
var sum = 1;
for (int j = i + x; j < xs.Count; j += x)
{
sum++;
dp2[i] -= dp2[j];
}
dp2[i] += ModInteger.Pow(sum, N);
}
for (int i = 100000; i >= 1; i--)
{
var sum = 0;
var p = 0;
if (xs[0] % i != 0) p += i - (xs[0] % i);
for (; p < xs.Count; p += i)
{
sum++; dp1[i] -= dp2[p];
}
for (int j = i * 2; j <= 100000; j += i)
dp1[i] -= dp1[j];
dp1[i] += ModInteger.Pow(sum, N);
}
return (int)dp1[1].num;
}
}
#region ModNumber
public partial struct ModInteger
{
public const long Mod = (long)1e9 + 7;
public long num;
public ModInteger(long n) : this() { num = n % Mod; if (num < 0) num += Mod; }
public override string ToString() { return num.ToString(); }
public static ModInteger operator +(ModInteger l, ModInteger r) { var n = l.num + r.num; if (n >= Mod) n -= Mod; return new ModInteger() { num = n }; }
public static ModInteger operator -(ModInteger l, ModInteger r) { var n = l.num + Mod - r.num; if (n >= Mod) n -= Mod; return new ModInteger() { num = n }; }
public static ModInteger operator *(ModInteger l, ModInteger r) { return new ModInteger(l.num * r.num); }
public static ModInteger operator ^(ModInteger l, long r) { return ModInteger.Pow(l, r); }
public static implicit operator ModInteger(long n) { return new ModInteger(n); }
public static ModInteger Pow(ModInteger v, long k)
{
ModInteger ret = 1;
var n = k;
for (; n > 0; n >>= 1, v *= v)
{
if ((n & 1) == 1)
ret = ret * v;
}
return ret;
}
}
#endregion
コメント
- メビウス関数とか使うともっと楽にできるっぽい．
