UOJ #188. 【UR #13】Sanrd

Description

给定 \(\sum_{i=l}^r f[i]\)

\(f[i]=\) 把 \(i\) 的每一个质因子都从小到大排列成一个序列(\(p_i^{c_i}\)要出现 \(c_i\) 次)后 , 第二大的质因子.

题面

Solution

符合 \(Min25\) 筛的处理顺序.

递归处理每个质因子作为次大值时的贡献,和不作为次大值时贡献的方案数 , 预处理一下区间质数个数就行了.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e6+10;

ll w[N],c[N],n,p[N];int m=0,sqr,cnt=0;

inline int id(ll x){return x<=sqr?x:m-(n/x)+1;}

inline ll S(ll n,int k){

	if(n<=p[k])return 0;

	ll ret=p[k]*(c[id(n)]-c[p[k]]);

	for(int i=k+1;i<=cnt && n/p[i]>=p[i];i++){

		for(ll j=n;(j/=p[i])>=p[i];)ret+=S(j,i)+p[i];

	}

	return ret;

}

inline ll solve(ll now){

	m=0,cnt=0,n=now,sqr=sqrt(n);

	for(ll i=1,j;i<=n;i=j+1)w[++m]=j=n/(n/i),c[m]=j-1;

	for(int i=2;i<=sqr;i++){

		if(c[i]==c[i-1])continue;

		p[++cnt]=i;

		for(int j=m;w[j]/i>=i;j--)c[j]-=c[id(w[j]/i)]-c[i-1];

	}

	return S(n,0);

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  ll l,r;

  cin>>l>>r;

  cout<<solve(r)-solve(l-1);

  return 0;

}

巴特西

UOJ #188. 【UR #13】Sanrd

Description

Solution

最新文章

热门文章