Counting Divisors HDU - 6069 (区间素数筛 + 一个数的所有素因子的个数 + 约数定理 + 数学)
程序员文章站
2022-06-08 12:10:35
...
In mathematics, the function d(n)d(n) denotes the number of divisors of positive integer nn.
For example, d(12)=6d(12)=6 because 1,2,3,4,6,121,2,3,4,6,12 are all 1212's divisors.
In this problem, given l,rl,r and kk, your task is to calculate the following thing :
InputThe first line of the input contains an integer T(1≤T≤15)T(1≤T≤15), denoting the number of test cases. For example, d(12)=6d(12)=6 because 1,2,3,4,6,121,2,3,4,6,12 are all 1212's divisors.
In this problem, given l,rl,r and kk, your task is to calculate the following thing :
(∑i=lrd(ik))mod998244353(∑i=lrd(ik))mod998244353
In each test case, there are 33 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107)l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).OutputFor each test case, print a single line containing an integer, denoting the answer.Sample Input
3 1 5 1 1 10 2 1 100 3Sample Output
10 48 2302
题意:输入 l r k 求 l<= t<=r, 求 对多有满足条件的t 的 d(t^k)=t^k的所有 不同因子的个数 的总和
思路:想求d(t^k),先求 d(t),根据约数定理 求不同因子的个数,先把 t 表示为不同素因子的积的形式;
n=p1^c1×p2^c2×p3^c3*…*pm^cm
d(n) = (C1 + 1)*(C2 + 1)*...... (Cm+1) ;表示不同因子的个数;
c1+1 为从中可以选出 1个p1,2个p1...... c1个p1,加 1就是 一个p1也不选,光p1这个素数就 c1+1 种情况,然后和其他选出的素因子结合;有一种情况就是 所有的素因子都不选,那么这种情况 就是 n个素因子为1 的这种情况;
理解了d(n),那么d(n^k)就好理解了
写代码应注意;
1,用三目运算符时,一定要加括号,就这道题而言,不加括号就是超时;
2,代码中用到了 区间素数筛, 还有最重要的时,a[] 和 sum[] 数组,sum[i] 存 sum[l+i] 的素因子个数;
a[i] = l + i; 找到 l+i的素因子时,一直除到不能整除 这个素因子位置;
3,当一个数 n,把1~根号n 中的素数 能除的都除尽了,但最终 n 不为1,那么这么剩余的n一定是个大素数;
我说这个大素数有两种情况 (1) n 本身为 素数 (2) n 把1~ 根号n中的素数除完之后,剩余的数为素数;
如 n = 14,14 把 1~根号14 中的素数都除尽后,剩下 7,7为素数;
代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
#define Max 1000000+10
#define mod 998244353
bool is_prime[Max]; // 0~Max 之间的素数
ll prime[Max]; // 存 0~Max 之间的素数;
ll sum[Max]; // sum[i]表示 l+i的因子个数;
ll a[Max]; // a[i] = l+i; 为了素数分解;
ll l,r,k;
ll num;
void Prime()
{
num = 0;
ll i,j;
memset(is_prime,true,sizeof(is_prime));
is_prime[0] = false;
is_prime[1] = false;
for(i = 2;i<Max;i++)
{
if(is_prime[i])
{
prime[num++] = i; // 找出1 ~ 1000000中的素数;
for(j = 2;i*j<Max;j++)
is_prime[i*j] = false;
}
}
}
int main()
{
Prime();
ll i,j,t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&l,&r,&k);
for(i = 0;i<=r-l;i++)
{
sum[i] = 1; // 要进行乘法,所以要赋值为1;
a[i] = l+i; // 为了把 a[i] == l+i 进行分解;
}
for(i = 0;i<num;i++)
{
ll temp = (l/prime[i]+((l%prime[i])?1:0))*prime[i];
// 三目运算符一定要加括号;,不加括号超时;
//找到[l,r]中第一个能被这个素数整除的数;
for(j = temp; j<=r; j += prime[i]) // 先找到能整除素数prime[i]的数;
{
ll res = 0;
while(a[j-l]%prime[i]==0) // 把这个数进行素数分解;
{
a[j-l] /= prime[i];
res++;
}
sum[j-l] = (sum[j-l]*((res*k+1)%mod))%mod;
}
}
ll res = 0;
for(i = 0;i<=r-l;i++)
{
if(a[i]!=1) sum[i] = sum[i]*(k+1)%mod; //分解之后,若不是1,一定是个大素数;
res = (res+sum[i])%mod;
}
printf("%lld\n",res);
}
return 0;
}