Counting Divisors
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 524288/524288 K (Java/Others)
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 :
(∑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).
Output
For each test case, print a single line containing an integer, denoting the answer.
Sample Input
3
1 5 1
1 10 2
1 100 3
Sample Output
10
48
2302
題目網址：http://acm.hdu.edu.cn/showproblem.php?pid=6069
分析
題意：
T
組測試資料，每組給出
l,r,k
，計算
l
到
r
每個數
k
次方的因子個數，并求和
可以推出規律：質數的
k
次方的因子個數為
k+1
比如求整數
a
的
k
次方的因子個數：
如果
a=6,k=2
，則
36
的因子有
1,2,3,4,6,9,12,18,36
總共
9
個
如果将
6
分解質因子，
6=2*3
2,3
都是質數，是以
6
的平方的因子數為
(k+1)*(k+1)
，即
3*3=9
可以得出規律：如果
a
分解質因子為
a=p[1]^x*p[2]^y*p[3]^z
（其中
p[1],p[2],p[3]
均為素數），則
a
的
k
次方的因子個數為：
(x*k+1)*(y*k+1)*(z*k+1)
（
a
的
k
次方分解質因子為
a^k=p[1]^(x*k)*p[2]^(y*k)*p[3]^(z*k)
）
是以可以将
l
到
r
每個數分解質因子，并記錄每個質因子出現的次數，然後根據上面的規律計算出每個數
k
次方的因子個數，求和即可
由于數值比較大，這道題很容易時間超限，是以要注意求解的方法，還要不斷取模
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
const int maxn=+;
const int mod=;
int tot,t;
ll l,r,k,ans,cnt[maxn],q[maxn],primes[maxn];
///cnt存放d(i^k)的值，q存放區間每個對應位置的數值
bool vis[maxn];
void init()///素數打表
{
for(int i=; i<maxn; i++)
{
if(!vis[i])///如果沒有被标記就存入素數數組
primes[tot++]=i;
for(int j=; j<tot; j++)///将素數i和他的倍數都标記
{
int k=i*primes[j];
if(k>maxn)break;
vis[k]=;
}
}
}
int main()
{
scanf("%d",&t);
init();
while(t--)
{
scanf("%lld%lld%lld",&l,&r,&k);
ans=;
if(l==) ans++,l++;
///1的多少次幂都是1，d(1)等于1
///是以如果左邊界是1，直接将ans加1，把左邊界移到2
for(ll i=; i<=r-l; i++) cnt[i]=,q[i]=l+i;
///将l到r對應位置的數值存入q，給cnt數組賦初值為1
for(ll i=; primes[i]*primes[i]<=r; i++)
{
ll j=l/primes[i]+(l%primes[i]!=);
///i和j來控制primes[i]*j在給定區間内
for( j=j*primes[i]; j<=r; j+=primes[i])
{
ll tmp=;
while(q[j-l]%primes[i]==) q[j-l]/=primes[i],tmp++;
///計算q[j-l]的因數中包含多少個primes[i]，存到tmp中
(cnt[j-l]*=(tmp*k)%mod+)%=mod;
///将因子數存入cnt[j-l]
}
}
for(ll i=; i<=r-l; i++)
{
if(q[i]!=) ans+=((k+)*cnt[i])%mod;
///q[i]不為1，說明q[i]的初值是l到r内的素數或其倍數
///由于前面已經控制了primes[i]*primes[i]<=r
///是以倍數在前邊已經計算出了并将其因子數存給了cnt[i]
///是以，隻用乘上k+1即可
else ans+=cnt[i];
ans%=mod;
}
printf("%lld\n",ans);
}
}