关键词：

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1215

题目描述：

七夕节

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



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

题目大意：

　　求因子之和

思路：

　　注意这里的因子不包含自身

　　化成因数乘积的形式，最后化成等比数列乘积

　　再模运算即可

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int N = 500010;
 8 
 9 struct Factor {
10     int p, e;
11     Factor(int p = 0, int e = 0) :p(p), e(e) {}
12 };
13 
14 bool not_prime[N] = { 1,1,0 };
15 vector<int> P;
16 
17 void E_prime() {
18     int m = (int)sqrt(N + 0.5);
19     for (int i = 2; i <= m; ++i)if (!not_prime[i])
20         for (int j = i*i; j < N; j += i)
21             not_prime[j] = true;
22     for (int i = 2; i < N; ++i)if (!not_prime[i])P.push_back(i);
23 }
24 
25 void Divided_by_Prime(int n, vector<Factor>& ve) {
26     double f = sqrt(n);
27     int t = 0;
28     for (int i = 0; P[i] <= f&&i < N; ++i)
29         if (n%P[i] == 0) {
30             ve.push_back(Factor(P[i], 1));
31             ++t, n /= P[i];
32             while (n%P[i] == 0) { n /= P[i]; ++ve[t - 1].e; }
33         }
34     if (!not_prime[n])ve.push_back(Factor(n, 1));
35 }
36 
37 int main() {
38     E_prime();
39     int t, n;
40     scanf("%d", &t);
41     while (t--) {
42         scanf("%d", &n);
43         vector<Factor> ve;
44         Divided_by_Prime(n, ve);
45         int sum = 1;
46         for (int i = 0; i < (int)ve.size(); ++i)
47             sum *= ((int)(pow(ve[i].p, ve[i].e + 1) + 1e-3) - 1) / (ve[i].p - 1);
48         printf("%d
", sum - n);
49     }
50 }

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

七夕节HDU-1215题目链接：https://vjudge.net/problem/HDU-1215#author=0题目：七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:"你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧!"人们纷纷来到告... 查看详情

hdu-1215七夕节

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

hdu1215.七夕节筛选法7月26

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

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

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

hdu1215七夕节

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

hdu1215七夕节

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

hdu1215(代码片段)

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

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

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

hdoj_1215_七夕节(代码片段)

AC代码：#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;longinthanshu(longinta)longintsum=1;longintbi=(int)sqrt((double)a);for(longinti=2;i<=bi;i++)if(a%i==0)su 查看详情

第四场hdu6069countingdivisors(逆向思维)

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

hdu6069countingdivisors

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

hdu1021(斐波那契数与因子3**)(代码片段)

题意是说在给定的一种满足每一项等于前两项之和的数列中，判断第n项的数字是否为3的倍数。斐波那契数在到第四十多位的时候就会超出int存储范围，但是题目问的是是否为3的倍数，也就是模3值为0，考虑到余数只有0，1，2，... 查看详情

hdu-5514frogs（容斥原理）

...青蛙，可以跳到的石头编号是gcd(ai,m)的倍数。2、枚举m的因子，若某个青蛙可以弹跳的石头编号中有该因子，那证明编号为这个因子的石头一定会被跳到，vis[i]=1。3、num[i]记录编号为i的石头被跳了几次，如果被跳的次数不等于应... 查看详情

完数[hdu1406]

完数TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):27275AcceptedSubmission(s):10213 ProblemDescription完数的定义：如果一个大于1的正整数的所有因子之和等于它的本身，则称这个数是完数，比如6，28都是完数：6 查看详情

4c-七夕节(代码片段)

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

hdu1999不可摸数(代码片段)

s(n)是正整数n的真因子之和，即小于n且整除n的因子和.例如s(12)=1+2+3+4+6=16.如果任何 数m，s(m)都不等于n,则称n为不可摸数. Input包含多组数据，首先输入T,表示有T组数据.每组数据1行给出n(2<=n<=1000)是整数。Output如果n是不... 查看详情

自然因子之和数学

【题目描述】两个自然数A和B.求A^B自然因子的总和。结果对9901取模输出【输入】两个自然数A和B,空格隔开。【输出】输出:和对9901取模的值。【输入样例】23【输出样例】15【样例解释】2^3=8自然因子8是:1、2、4、8。他们的sum是15... 查看详情

求一个数的因子之和(代码片段)

直接求解LLfactor(LLx) LLcnt=0; for(inti=1;i<=sqrt(x);i++) if(x%i==0) if(x/i==i)cnt+=i;//ex:9=3*3 elsecnt+=i+x/i; returncnt;筛法LLsum[MS];voidfactor_sieve()//sum[i]记录数i的各个因子之和 for(inti=1;i& 查看详情