AtCoder ABC #227 (キーエンスプログラミングコンテスト2021-Nov.) : G - Divisors of Binomial Coefficient

なんとか全完。
https://atcoder.jp/contests/abc227/tasks/abc227_g

問題

正整数N,Kが与えられる。
Binom(N,K)の約数は何通りか。
Nの上限は10^12、Kの上限は10^6である。

解法

Binom(N,K)を素因数分解できれば、(各素因数の次数+1)を掛け合わせたものが解となる。
あとは各素因数の次数を求めよう。
そのためには、Binom(N,K)は[N-(K+1),N]の範囲の整数を掛けたものから、[1,K]の範囲の整数を掛けたものを割ったものなので、[N-(K+1),N]及び[1,K]の範囲の各整数を素因数分解すればよい。

まず素因数として2～10^6の範囲で篩にかけよう。
この時点で、[1,K]の範囲の各整数は素因数分解が完了する。
また、[N-(K+1),N]について2～10^6の範囲の整数で割れるだけ割ったとき、それでも2以上の値が残ったら、それはもう単一の素数である(N≦(10^6)^2なので、10^6以上の素因数を2つ以上掛けた形になることはない。)

ll N,K;

ll A[2010101];
ll B[2010101];
map<int,ll> num;
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll ret=1;
	for(i=0;i<=K;i++) A[i]=i;
	FOR(i,K) B[i]=N-i;
	for(i=2;i<=1000000;i++) {
		for(j=i;j<=K;j+=i) {
			while(A[j]%i==0) {
				A[j]/=i;
				num[i]--;
			}
		}
		ll s=N-K+1;
		for(ll t=(s+(i-1))/i*i;t<=N;t+=i) {
			k=N-t;
			while(B[k]%i==0) {
				num[i]++;
				B[k]/=i;
			}
		}
	}
	FOR(i,K) if(B[i]>1) ret=ret*2%mo;
	FORR2(a,b,num) {
		ret=ret*(b+1)%mo;
	}
	cout<<ret<<endl;
}

まとめ

E,Fに比べると、解法に迷わないかも。