正文

hdu6069countingdivisors

声声醉如兰  声声醉如兰  2022-09-13  578

关键词：

题意：给出求L,R 之间的数的K次方的因子数之和

思路：打表求出1~10^6之间的素数，枚举[L,R]之间素数的倍数，然后按算数基本定理求出因子个数和。处理过后[L,R]之间的数要么是1，要么是一个素数，再次根据算数基本定理计算因子个数和。

#include<bits/stdc++.h>
#define MAXSIZE 1000015
#define INF 0x3f3f3f3f
#define LL long long
#define MOD 998244353
using namespace std;

bool vis[MAXSIZE];
LL p[MAXSIZE],a[MAXSIZE],b[MAXSIZE];
int n,cns;

void GetPrime()
{
    cns = 1;
    memset(vis,false,sizeof(vis));
    vis[1] = true;
    for(int i=2;i<MAXSIZE;i++)
    {
        if(vis[i] == false)
        {
            p[cns++] = i;
            for(int j=i*2;j<MAXSIZE;j+=i)
            {
                vis[j] = true;
            }
        }
    }
}

int main()
{
    GetPrime();
    LL l,r,k,ans;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&l,&r,&k);
        ans = 0;
        for(LL i=l;i<=r;i++)
        {
            a[i-l] = i; //记录这个数的值
            b[i-l] = 1; //记录正因子个数
        }

        for(int i=1;p[i]*p[i]<=r && i<=cns;i++) //枚举素数
        {
            LL j = l/p[i] + (l%p[i]!=0);
            for(j=j*p[i];j<=r;j+=p[i]) //枚举素数的倍数
            {
                LL sum = 0;
                while(a[j-l]%p[i] == 0)
                {
                    sum++;
                    a[j-l]/=p[i];
                }
                b[j-l] = (b[j-l]*((sum*k%MOD + 1)%MOD))%MOD; 
            }
        }

        for(LL i=l;i<=r;i++)
        {
            if(a[i-l] == 1)
                ans = (ans+b[i-l])%MOD;
            else
                ans = (ans+b[i-l]*(k+1)%MOD)%MOD;
        }

        printf("%lld
",ans);
    }
    return 0;
}

View Code

hdu6069countingdivisors

题意：给出求L,R之间的数的K次方的因子数之和思路：打表求出1~10^6之间的素数，枚举[L,R]之间素数的倍数，然后按算数基本定理求出因子个数和。处理过后[L,R]之间的数要么是1，要么是一个素数，再次根据算数基本定理计算... 查看详情

hdu6069多校countingdivisors

　　　　　思路：对于n^k其实就是每个因子的个数乘了一个K。然后现在就变成了求每个数的每个质因子有多少个，但是比赛的时候只想到sqrt(n)的分解方法，总复杂度爆炸，就一直没过去，然后赛后看官方题解感觉好妙啊！通过... 查看详情

hdu6069countingdivisors——2017multi-universitytraining4

CountingDivisorsTimeLimit:10000/5000MS(Java/Others) MemoryLimit:524288/524288K(Java/Others)TotalSubmission(s):2599 AcceptedSubmission(s):959ProblemDescrip 查看详情

hdu6069countingdivisors（唯一分解定理+因子数）

http://acm.hdu.edu.cn/showproblem.php?pid=6069题意：思路：根据唯一分解定理，$n={a_{1}}^{p1}*{a2_{}}^{p2}...*{a_{m}}^{pm}$，那么n的因子数就是n的k次方也是一样的，也就是p前面乘个k就可以了。先打个1e6范围的素数表，然后枚举每个素数，在... 查看详情

第四场hdu6069countingdivisors(逆向思维)

http://acm.hdu.edu.cn/showproblem.php?pid=6069题目大意：求i从l到r中i的k次方的因子数之和。解题思路：我们可以知道一个数有因子，则这个数的因子一定是若干个质数因子排列组合得到的。我们首先要得到10^6中的素数，然后它的因子数... 查看详情

区间筛2-17多校训练四hdu6069countingdivisors

http://acm.hdu.edu.cn/showproblem.php?pid=6069【题意】给定l,r,k，求d(n)是n的因子个数【思路】【Accepted】1#include<iostream>2#include<cstdio>3#include<cstring>4#include<string>5#include<cmath> 查看详情

hdu6069countingdivisors

//变量命名很重要你看我抄队友的代码抄一遍就t了再改还是t我以为是我不够大力原来是这个变量名弄的太混乱了--搞了好半天才发现哈哈 //有一个很重要的定理是一个数的因数个数和他的素数幂次乘积表达式的关系哈哈当时... 查看详情

hdu6069countingdivisors（区间素数筛法）

题意：。。。就题面一句话思路：比赛一看公式，就想到要用到约数个数定理约数个数定理就是：对于一个大于1正整数n可以分解质因数：则n的正约数的个数就是对于n^k其实就是每个因子的个数乘了一个K然后现在就变成了求每... 查看详情

countingdivisorshdu-6069

CountingDivisors HDU-6069 题意：给定区间[a,b]和k，求xk有多少因子（x属于[a,b]），求和。题解：http://blog.csdn.net/zlh_hhhh/article/details/76680641a、b最大可达到1e12，但是b-a<1e6。一开始愚蠢的一个一个分解然后去求有多少因子然后求... 查看详情

hdu6069

CountingDivisorsProblemDescriptionInmathematics,thefunction d(n) denotesthenumberofdivisorsofpositiveinteger n.Forexample, d(12)=6 because 1,2,3,4,6,12 areall 1 查看详情

hdu6069[素数筛法]2017多校3

/*hdu6069[素数筛法]2017多校3*/#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;LLl,r,k;constLLMOD=998244353LL;intT,n,prime[1100000],primesize;boolisprime[11000000];voidgetlist(intlistsize){m 查看详情

hdu6069

思路：n=p1^x1*p2^x2....pm^xm，则p的约数个数为(x1+1)*(x2+1)....(xm+1)，那么n^k=p1^(x1+k)....pm^(xm+k),约数个数为(x1*k+1)*....*(xm*k+1)。　　先求出1-1e6内的质数，再对l--r之间的数求xi1#include<bits/stdc++.h>2usingnamespacestd;3typedef 查看详情

hdu6069(简单数学+区间素数晒法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6069 题意:给出l,r,k．求：(lambdad(i^k))mod998244353，其中l<=i<=r,d(i)为i的因子个数．思路：若x分解成质因子乘积的形式为x=p1^a1*p2^a2*...*pn^an，那么d(x)=(a1+1)*(a2+1)*...*(an 查看详情

hdu6069,2017多校1003

这是一道区间素数筛的题目，首先线性筛出1e6的素数,然后用每一个素数对区间内的数进行素数分解公式:求某个数的因子个数，先进行素数分解x=p1^z1*p2^z2*p3^z3;然后sum=(z1+1)*(z2+1）*(z3+1);1#include<cstdio>2typedeflonglongll;3constintN=100001... 查看详情

hdu6069multi-4素数筛

被这一道题打崩，打表的题目啊~~~~类似大区间的素数筛法(POJ2689)题目链接约数和定理：d(n)=(a1+1)(a2+1)……(an+1){ai指的是质因数分解后质数pi的个数}代码：#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#defin... 查看详情

hdu3308(线段树区间合并)

LCISTimeLimit:6000/2000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):6069 AcceptedSubmission(s):2635ProblemDescriptionGivenninte 查看详情

[spoj]countingdivisors(cube)

来自FallDream的博客，未经允许，请勿转载，谢谢。设d(x)表示x的约数个数，求$sum_{i=1}^{n}d(i^{3})$ Thereare5Inputfiles. -Input#1:1≤N≤10000,TL=1s. -Input#2:1≤T≤300 查看详情

hdoj6069素数筛法（数学）

CountingDivisorsTimeLimit:10000/5000MS(Java/Others) MemoryLimit:524288/524288K(Java/Others)TotalSubmission(s):3041 AcceptedSubmission(s):1130ProblemDescri 查看详情