首页 > 代码库 > HDU 6069
HDU 6069
Counting Divisors
Problem Description
In mathematics, the function d(n) denotes the number of divisors of positive integer n.
For example, d(12)=6 because 1,2,3,4,6,12 are all 12‘s divisors.
In this problem, given l,r and k, your task is to calculate the following thing :
For example, d(12)=6 because 1,2,3,4,6,12 are all 12‘s divisors.
In this problem, given l,r and k, your task is to calculate the following thing :
(∑i=lrd(ik))mod998244353
Input
The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.
In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).
In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).
Output
For each test case, print a single line containing an integer, denoting the answer.
Sample Input
31 5 11 10 21 100 3
Sample Output
10482302
这题实质上就是分解质因数，不过不能对每个数都分解一次，这样肯定超时。
要用线性的方法求质因数。
设i可以分解为a1,a2,a3,a4……am,则总数加上（a1*k+1)*(a2*k+1)*……(am*k+1)
#include<cstdio>#include<cstring>#include<iostream>#include<cmath>#define ll long longusing namespace std;#define ll long longconst int mod=998244353;const int maxn=1000005;int prime[maxn];bool vis[maxn];int top;ll a[maxn];ll b[maxn];void pri(){ top=0; memset(vis,0,sizeof vis); vis[1]=1; for(int i=2; i<maxn; i++) { if(!vis[i]) prime[top++]=i; for(int j=0; j<top&&i*prime[j]<maxn; j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) break; } }}void fun(ll l,ll r,ll k){ for(ll i=l; i<=r; i++) b[i-l]=i; for(ll i=l; i<=r; i++) a[i-l]=1; for(ll i=0; i<top&&prime[i]<=sqrt(r); i++) { ll x=l/prime[i]; if(x*prime[i]<l) x++; for(ll j=x; j*prime[i]<=r; j++) { ll s=0; while(b[prime[i]*j-l]%prime[i]==0) { s++; b[prime[i]*j-l]/=prime[i]; } a[prime[i]*j-l]=a[prime[i]*j-l]*(s*k+1)%mod; } } for(ll i=l; i<=r; i++) if(b[i-l]>1) a[i-l]=a[i-l]*(k+1)%mod;}int main(){ pri(); int T; scanf("%d",&T); while(T--) { ll l,r; ll k; scanf("%lld%lld%lld",&l,&r,&k); ll sum=0; fun(l,r,k); for(ll i=l; i<=r; i++) sum=(sum+a[i-l])%mod; printf("%lld\n",sum); } return 0;}
HDU 6069
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。