読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

AtCoder ARC #034 : C - 約数かつ倍数

ARC

Cもいつもより易しめ。
http://arc034.contest.atcoder.jp/tasks/arc034_3

問題

正整数A,Bがある。
A!の倍数でB!の約数となる整数はいくつあるか。

解法

A!の倍数でB!の約数となる整数は、(B!/A!の約数)*(A!)ということになる。
よってB!/A!の約数を求めればよい。
幸いBとAの差は小さいので、(A+1)、(A+2)、…、Bをそれぞれ素因数分解して各素因数の次数を足し合わせ、各素因数の(次数+1)を掛け合わせればよい。

ll A,B;
ll mo=1000000007;

map<ll,int> enumdiv(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	map<ll,int> H,T;
	
	for(i=B+1;i<=A;i++) {
		T=enumdiv(i);
		ITR(it,T) H[it->first]+=it->second;
	}
	ll ret=1;
	ITR(it,H) ret = ret*(it->second+1)%mo;
	cout<<ret<<endl;
	
}

まとめ

ここまでは順調。

広告を非表示にする