正文

七夕节hdu-1215(唯一分解素数筛法因子之和加强版)(代码片段)

RUBY-WOO  RUBY-WOO  2022-12-22  232

关键词：

七夕节 HDU - 1215

题目链接：https://vjudge.net/problem/HDU-1215#author=0

题目：

七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:"你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧!"
人们纷纷来到告示前,都想知道谁才是自己的另一半.告示如下:

数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.
你想知道你的另一半吗?

Input输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).
Output对于每组测试数据,请输出一个代表输入数据N的另一半的编号.
Sample Input

Sample Output

1
8
22

思路：这道题数据有点弱，可以直接取巧打个素数表将因子累加即可，但是如果数据很大的话，就要将其优化，就要采取唯一分解的这个算术基本算法
所以要利用其中的因子和来计算：

代码如下：

//
// Created by hanyu on 2019/8/10.
//
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
using namespace std;
const int maxn=1e6+1000;
int prime[maxn],isprime[maxn];
void getp()

    memset(isprime,1,sizeof(isprime));
    int limit=(int)sqrt(maxn*1.0);
    for(int i=2;i<limit;++i)
    
        if(isprime[i])
        
            for(int j=i*i;j<maxn;j+=i)
            
                isprime[j]=0;
            
        
    
    for(int i=2,j=0;i<maxn;i++)
        if(isprime[i])
            prime[j++]=i;

int fenjie(int n)

    int num,sum,total=1;
    int nn=n;
    int limit=sqrt(maxn*1.0);
    for(int i=0;prime[i]*prime[i]<=n;++i)
    
        num=sum=1;
        if(n==1)
            break;
        while(n%prime[i]==0)
        
            num*=prime[i];
            n/=prime[i];
            sum+=num;
        
        total*=sum;
    
    if(n!=1)
        total*=(n+1);
    return total-nn;

int main()

    getp();
    int T;
    int num;
    scanf("%d",&T);
    while(T--)
    

        scanf("%d",&num);
        if(num==1)
        
            printf("0\\n");
            continue;
        
        else if(isprime[num])
        
            printf("1\\n");
            continue;
         else
            printf("%d\\n",fenjie(num));
    
    return 0;

hdu1215七夕节

题意：求因子之和。注意：1的因子之和是1。数字N的因子就是全部比N小又能被N整除的全部正整数,如12的因子有1,2,3,4,6。importjava.util.Scanner;publicclassMain{ publicstaticvoidmain(String[]args){ Scannersc=newScanner(System.in); intt=sc.nextInt(); whil 查看详情

hdu1215七夕节-(埃氏筛+唯一分解定理)(代码片段)

七夕节TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):56666 AcceptedSubmission(s):18239ProblemDescription七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人... 查看详情

hdu1215求约数和唯一分解定理的基本运用

...problem.php?pid=1215题意：求解小于n的所有因子和利用数论的唯一分解定理。若n=p1^e1*p2^e2*……*pn^en(任何一个数都可以分解成素数乘积) 则n的因子个数为 (1+e1)(1+e2)……(1+en) n的各个因子的和为(1+p1+p1^2+……+p1^e1)(1+p2+p2^2+…... 查看详情

hdu-1215七夕节

...的所有因子和。解题思路：暴力找出所有因子求和题目：七夕节TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSu 查看详情

hdu1215.七夕节筛选法7月26

七夕节七夕节那天,月老来到数字王国,他在城门上贴了一张告示,而且和数字王国的人们说:"你们想知道你们的还有一半是谁吗?那就依照告示上的方法去找吧!"人们纷纷来到告示前,都想知道谁才是自己的还有一半.告演示样... 查看详情

hdu6069countingdivisors（区间素数筛法）

...个数定理约数个数定理就是：对于一个大于1正整数n可以分解质因数：则n的正约数的个数就是对于n^k其实就是每个因子的个数乘了一个K然后现在就变成了求每个数的每个质因子有多少个，但是比赛的时候只想到sqrt(n)的分解方法... 查看详情

hdu1215七夕节

七夕节TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):47104 AcceptedSubmission(s):15117ProblemDescription七夕节那天,月老来查看详情

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

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

hdu1215七夕节

对于每个数我们筛一下它的因数，但是不能用O(N)的算法一个一个去筛。而要用O($sqrt{N}$)算法筛。和上道欧拉函数的题目同一个思想。#include<cstdio>#include<algorithm>intT;intx;intmain(){scanf("%d",&T);while(T--){intans=0;scanf("%d",&x);... 查看详情

fzu1075分解素因子数论/唯一分解定理/分解素因子裸模板

【唯一分解定理】：https://www.cnblogs.com/mjtcn/p/6743624.html假设x是一个正整数，它的值不超过65535(即1<x<=65535)，请编写一个程序，将x分解为若干个素数的乘积。Input输入的第一行含一个正整数k(1<=k<=10)，表示测试例的个数，... 查看详情

hdu1215(代码片段)

HDU1215七夕节思路：求一个数的约数和。一：打表#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintmaxn=5e5+10;intsum[maxn];voidinit 查看详情

唯一分解定理（以minimunsumlcmuva10791为例）

唯一分解定理是指任何正整数都可以分解为一些素数的幂之积，即任意正整数n=a1^p1*a2^p2*...*ai^pi；其中ai为任意素数，pi为任意整数。题意是输入整数n，求至少2个整数，使得它们的最小公倍数为n，且这些整数的和最小，输出最小... 查看详情

数学基础素数线性筛法--欧拉筛法模板普通筛法的优化

质数（素数）：指大于1的所有自然数中，除了1和自身，不能被其它自然数整除的数合数：比1大，但不是素数的数称为合数，合数除了被1和自身整除，还能被其它数整除质因数（素因数或质因子）：能整除给定正整数的质数，... 查看详情

求素数（从判断素数到筛法）(代码片段)

判断素数最简单的判断就是根据素数的定义：只有两个因子1和本身（1不是素数）。时间复杂度O(n)boolis_prime(intx)if(x==1)returnfalse;rep(i,2,n-1)if(x%i==0)returnfalse;returntrue;我们知道因子都是成对出现的，所以在枚举时，可以只枚举2-(sqrtx).... 查看详情

一般筛法求素数+快速线性筛法求素数

素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子2。。N^(0.5)，看看能否整除N。如果需要判断的次数较多，则先用下面介绍的办法预处理... 查看详情

转载一般筛法求素数+快速线性筛法求素数

素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子2。。N^(0.5)，看看能否整除N。如果需要判断的次数较多，则先用下面介绍的办法预... 查看详情

codeforces757b：bash'sbigday（分解因子+hash）

http://codeforces.com/problemset/problem/757/B题意：给出n个数，求一个最大的集合并且这个集合中的元素gcd的结果不等于1。思路：一开始把素数表打出来，发现有9k+个数，不能暴力枚举。发现O（sqrt（n）*n）似乎可行，就枚举因子，然后... 查看详情

a^b的约数（因子）之和对mod取模(代码片段)

POJ1845首先把A写成唯一分解定理的形式分解时让A对所有质数从小到大取模就好了然后就有：A=p1^k1*p2^k2*p3^k3*...* pn^kn然后有： A^B=p1^(k1*B)*p2^(k2*B)*...*pn^(kn*B);约数和公式：对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)有A... 查看详情