Codeforces #738 Div2 : E. Mocha and Stars

こちらもDiv2最終問の割に正答者多め。
https://codeforces.com/contest/1559/problem/E

問題

整数N,Mが与えられる。
N要素の整数列Aを考える。
この時、各要素の上限L[i]下限R[i]が与えられており、L[i]≦A[i]≦R[i]でなければならない。
加えて、Aの総和がM以下であるものとする。

条件を満たすAのうち、全要素のGCDが1となるのは何通りか。

解法

f(n) := GCDがnとなる組み合わせ
g(n) := GCDがnの倍数となる組み合わせ

とすると、
f(n) = g(n) - f(2n) - f(3n) - ....
なので、f(n)を大きい順に求めて行けばよい。
g(n)を求めるのはO(N(M/n))で求められるので、全体でもO(N MlogM)程度で求められるはず。

int N,M;
int L[55],R[55];
ll from[1010101];
ll to[1010101];
ll gcdp[101010];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>L[i]>>R[i];
	
	for(x=M;x>=1;x--) {
		int ma=M/x;
		FOR(y,ma+2) from[y]=0;
		from[0]=1;
		FOR(i,N) {
			FOR(y,ma+2) to[y]=0;
			int l=(L[i]+x-1)/x;
			int r=R[i]/x;
			if(l>r) break;
			FOR(y,ma+1) {
				(to[min(ma+1,y+l)]+=from[y])%=mo;
				(to[min(ma+1,y+r+1)]+=mo-from[y])%=mo;
			}
			FOR(y,ma+2) (to[y+1]+=to[y])%=mo;
			FOR(y,ma+2) from[y]=to[y];
		}
		if(i<N) continue;
		FOR(y,ma+1) (gcdp[x]+=from[y])%=mo;
		for(j=x*2;j<=M;j+=x) gcdp[x]+=mo-gcdp[j];
		gcdp[x]%=mo;
		
	}
	cout<<gcdp[1]<<endl;
	
}

まとめ

3000ptの問題の割には簡単な気が。