关键词：

七夕节

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 56666    Accepted Submission(s): 18239

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



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

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
#define ll long long
int ans[500005];
void init()

    memset(ans,0,sizeof(ans));
    for(int i=1;i<500005;i++)//因子的大小
        for(int j=i;j<500005;j=j+i)//把i的倍数都累加i这个因子
            ans[j]+=i;


int main()///hdu1215，唯一分解定理
//求小于n的因子数的和。比如12， 1 2 3 4 6
    int t;
    scanf("%d",&t);
    init();
    while(t--)
    
        int n;
        scanf("%d",&n);
        printf("%d
",ans[n]-n);//打表的时候把自己也算进去，输出答案要减去本身

    
    return 0;

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 查看详情

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七夕节

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

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七夕节（因子之和）

...接：　　http://acm.hdu.edu.cn/showproblem.php?pid=1215题目描述：七夕节 ProblemDescription七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:"你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧!"... 查看详情

hdu1215七夕节

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

hdu3826-squarefreenumber-(欧拉筛+唯一分解定理)(代码片段)

SquarefreenumberTimeLimit:10000/3000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):3691    AcceptedSubmission(s):971 ProblemDescriptionInmathematics,asquarefreenumberisonewhichisdivisiblebynoperfectsquares,except1.Forexample,10... 查看详情

hdu1215.七夕节筛选法7月26

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

hdu2012素数判断方式(代码片段)

复习了一下素数埃氏筛线性筛埃氏筛和线性筛可以优先筛选出素数，从而节省时间哦线性筛应该挺好理解的 埃氏筛就是i%prime[j]这里可能不太好理解可以举几下例子就会慢慢懂的举了例子下次再看 脑海里就会自动浮现当... 查看详情

hdu5505-gtandnumbers-(贪心+gcd+唯一分解定理)(代码片段)

GTandnumbersTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):2772    AcceptedSubmission(s):688ProblemDescriptionYouaregiventwonumbersN andM.EverystepyoucangetanewN inthewaythatmultiplyN byafactorofN&n... 查看详情

hdu1215(代码片段)

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

hdu4497-gcdandlcm-(欧拉筛+唯一分解定理+组合数)(代码片段)

GCDandLCMTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):3409    AcceptedSubmission(s):1503ProblemDescriptionGiventwopositiveintegersGandL,couldyoutellmehowmanysolutionsof(x,y,z)thereare,satisfyingthatgcd(x,y,z)=Ga... 查看详情

hdu2421-decipheringpassword-（欧拉筛+唯一分解定理+积性函数+立方求和公式）(代码片段)

DecipheringPasswordTimeLimit:5000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):2357    AcceptedSubmission(s):670ProblemDescriptionXiaominghasjustcomeupwithanewwayforencryption,bycalculatingthekeyfromapubliclyviewablenumberinth... 查看详情

埃氏筛法

/*2|埃式筛法|3|快速筛选素数|　　　　|15-7-26|4*/#include<iostream>#include<cstdio>usingnamespacestd;constintSIZE=1e7;intprime[SIZE];//第i个素数boolis_prime[SIZE];//true表示i是素数intslove(intn){intp=0;for(inti=0 查看详情

埃氏筛法

埃氏筛法，理解起来很好理解，就是在1~n这n个连续的数里面开始筛出合数，知道剩下全部为素数，大致流程如下：第一步：能够确定1不是素数，所以将1筛出，剩下从2开始的数列第二步：找到2为第一个素数，那么遍历这个数列... 查看详情

唯一分解定理

整数的唯一分解定理对于一个大于1正整数n可以分解质因数：  查看详情

埃氏筛法(代码片段)

埃氏筛法的基本思想：这个东西的基本思路就是首先把1~n中小于2的数先标记，因为这些数字都不是质数。之后我们依次标记这个里面所有质数的倍数，直到这个质数的平方要大于n的时候，我们就停止这个程序。这样我们剩下没... 查看详情