SRM613 Div1 Medium - RandomGCD

TopCoder SRM

http://compro.tsutajiro.com/archive/181015_incexc.pdf
(包除原理 解ける数え上げの範囲を広げよう - tsutaj)
今の俺が求めていたものはこれだった
包除原理を極め鯛

問題

L以上r以下の整数を重複を許してn個選んで数列を作る
全要素のgcdがkになるような数列はいくつあるか

1 <= n, k, L <= 10^9
L <= r <= 10^9
0 <= r-L <= 10^5

解法

数列の要素として使えるのはL以上r以下のkの倍数のみ
そこで L = ceil(L/k), r = floor(r/k) とし、
「L以上r以下の整数のみからなる長さnの数列のうち、全要素のgcdが1になるようなものの個数」
を求めることにする

f(g): L以上r以下の整数のみからなる長さnの数列のうち、全要素のgcdがg以上になるようなものの個数
とすると、答えは包除原理の要領で
Σ f(g) * (-1)^(gの素因数の個数) (g: 同じ素因数で2度以上割り切れないような整数)
となる

素因数で2度以上割り切れないような整数 っていう条件はどういうことかというと
例えばg=4のケースは、g=1で足されてg=2で引かれてちょうど相殺されているから、足したり引いたりする必要がない
(g=12なんかも同様に、g=1で+、g=2で-、g=3で-、g=6で+ と既に消えている)

するとgの上限はどこまで考えればいいかが問題になる
1からRまで全部試せればそれでいいけど制約的に無理
そこで↑のΣで足し合わせるとき、L以上r以下の範囲に条件を満たす数が2個以上存在するようなもののみ考えることにする
(∵ 1個しか存在しない場合は当然同じ数字xがn個続く数列になり、gcdはxになるため、(x=1でない限りは)どうせ答えに影響しないから)
こうするとgは1からr-Lまで考えれば十分になる
(∵ L以上r以下の範囲にr-L+1以上の整数の倍数が2度以上現れることはないため)
L=1のときのみ答えに+1してやればok

実装

pf(n)はnの素因数一覧を重複なしで返すようになってる
だからこれの積がnと一致しなかったら素因数の重複があるってことになるから、
↑で言ったように足しも引きもしない

accumulateがあるなら積バージョンもあるんじゃね？ってずっと思ってたんだけど、
ググってみたらコードの通り
accumulate(a.begin(), a.end(), s, multiplies＜int＞())
とか書くとs * (指定範囲の各要素の積)を計算してくれるらしい
滅多に使わないけど覚えておこう

足し引きする値は、L以上r以下のうちiで割り切れる整数の個数を
m = floor(r/k) - floor((L-1)/k)
として、
(m個の整数から1個選ぶのをn回繰り返す) - (同じ整数をn回繰り返す数列の個数)
= n^m - m
となる

class RandomGCD {
public:
	vector<int> pf(int n) {
		vector<int> res;
		for (int i = 2; i*i <= n; i++) if (n%i==0) {
			res.push_back(i);
			while (n%i==0) n /= i;
		}
		if (n!=1) res.push_back(n);
		return res;
	}

	int countTuples(int n, int k, int l, int r) {
		l = (l+k-1)/k, r = r/k;
		if (r<l) return 0;
		ll res = (l==1);
		reps(i,1,r-l+1) {
			vector<int> p = pf(i);
			if (i!=1 && accumulate(all(p),1,multiplies<int>())!=i) continue;
			int m = r/i - (l-1)/i;
			(res += (mop(m,n)-m) * (i==1 || p.size()%2==0 ? 1 : -1)) %= mod;
		}
		(res += mod) %= mod;
		return (int)res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=13016&rd=15846