正文

hdu1215.七夕节筛选法7月26

cynchanpin  cynchanpin  2022-09-08  279

关键词：

七夕节

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

技术分享

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

Input

输入数据的第一行是一个数字T(1<=T<=500000),它表明測试数据的组数.然后是T组測试数据,每组測试数据仅仅有一个数字N(1<=N<=500000).

Output

对于每组測试数据,请输出一个代表输入数据N的还有一半的编号.

Sample Input

321020

Sample Output

非常显然，穷举是不行滴~

类似筛选法找因子的和。

#include<iostream>
#include<cstdio>
using namespace std;
int f[500001]={0};
int main()
{
    for(int i=1;i<=500000;i++)
        f[i]=1;
    for(int i=2;i<=250001;i++){
        for(int j=i+i;j<=500000;j+=i)
            f[j]+=i;
    }
    int T,x;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&x);
        printf("%d
",f[x]);
    }
    return 0;
}

然后上一点筛选法的知识：

筛选法

筛选法又称筛法，是求不超过自然数N（N＞1）的全部质数的一种方法。

据说是古希腊的埃拉托斯特尼（Eratosthenes。约公元前274～194年）发明的，又称埃拉托斯特尼筛子。

　　详细做法是：先把N个自然数按次序排列起来。

1不是质数，也不是合数，要划去。第二个数2是质数留下来。而把2后面全部能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面全部能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面全部能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。由于希腊人是把数写在涂腊的板上，每要划去一个数。就在上面记以小点。寻求质数的工作完成后。这很多小点就像一个筛子。所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”。简称“筛法”。（还有一种解释是当时的数写在纸草上，每要划去一个数。就把这个数挖去。寻求质数的工作完成后，这很多小洞就像一个筛子。）

hdu-1215七夕节

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

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

hdu1215(代码片段)

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

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

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

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

历史上的今天7月26日：工业机器人之父诞生；《计算机欺诈和滥用法》首次应用；at&t合作微软

整理|王启隆透过「历史上的今天」，从过去看未来，从现在亦可以改变未来。今天是2022年7月26日，在1978年的今天，第一个试管婴儿在伦敦诞生。这是一对伦敦夫妇莱斯利·布朗和她的丈夫约翰的孩子，婴儿重... 查看详情

月2周5（前半写于周2）

...个人也能活下去》6/12《异世界和我，你喜欢哪一个》（七夕节狗粮啊）5/12《自称贤者弟子的贤者》4/12《异世界料理道》7/12《精灵幻想记》3/12《说谎的天使死了》9/12《欢迎来到实力至上主义教室》8/12《庶民样本（完结卷）》6/... 查看详情

浓情七夕，有礼相送！

农历7月7日是中国的传统佳节七夕节，因牛郎和织女的美丽爱情传说，使其成为了象征爱情的节日，从而被认为是中国最具浪漫色彩的传统节日——中国情人节。借着这个浪漫的日子，《新程序员》祝福所有程序... 查看详情

hdu4033

1/*2http://acm.hdu.edu.cn/showproblem.php?pid=40333题意:正n边形里面有一个点,知道这个点到n个顶点的距离,要求这个正多边形的边长4思路:在(0,20000)二分查找答案,用上余弦定理52017年02月26日19:38:146*/7#include<cstdio>8#include<cmath>9doublelen[... 查看详情

七夕情人节是不是该有个logo

背景七夕节，又名乞巧节、七巧节或七姐诞，发源于中国，是传统民间重要的节日之一。也是东亚各国的传统节日，在农历七月初七庆祝（日本在明治维新后改为阳历7月7日），来自于牛郎与织女的传说。你朋友圈开始... 查看详情

7月26

Softlimit软限制：不会拒绝你的工作，只会给你警告hardlimit硬限制Xhost+ 都有权限加载桌面Dbsnmp简单网络管理协议。Unicode统一编码配置yum：#rm-f/etc/yum.repos.d/* 配置yum文件#vi/et 查看详情

七夕送礼，让《新程序员》伴你一“杯”子！

4号团队-团队任务3:每日立会（11月26日至12月7日）

...菊，产品经理王擎，软件工程师。共三人每日例会11月26日至12月7号的链接：26日 https://www.cnblogs.com/jbbrnbs/p/10028609.html27日 https://www.cnblogs.com/jbbrnbs/p/10028 查看详情

约“惠”七夕--今年的七夕来点实际的

一眨眼一年一度的“七夕”来到了......朋友圈又要开始了无聊的秀恩爱，虐“狗”刷屏了，难道我们的“七夕”就这么无聊的过去了么？答案是NO！NO！NO！51CTO学院在“七夕”当天会进行全站的优惠活动，今年我们屏蔽秀恩爱！... 查看详情