标签 - 筛法

? 解题记录 ? ? 洛谷 ? ? 组合数 ? ? 筛法 ?    2018-11-04 15:28:51    671    0    0
2.1 题目描述 九条可怜是一个热爱游戏的女孩子,她经常在网上和一些网友们玩一款叫做《僵尸危机》 游戏。 在这款游戏中,玩家们会需要在成为僵尸之前与黑恶势力斗智斗勇,逃离被病毒感染的小 岛。但是黑恶势力不会让玩家轻易得逞,他会把一些玩家抓走改造成僵尸。变成僵尸的玩家会 攻击其他的玩家,被攻击的玩家会被” 感染”,成为病毒的潜在宿主。 具体来说,游戏开始时,所有的玩家会获得一个 l ∼ r 的编号 (如果一共有 r − l + 1 个玩 家),不同的玩家的编号不同。 游戏分轮次进行,在每一轮中一次会发生这样的事情。 • 如果所有当前所有的正常人都已经被感染,那么游戏结束。 •
? 解题记录 ? ? UVa ? ? 筛法 ?    2017-09-14 21:19:03    492    0    0
这是蓝书上一道很经典的数论题,位于P124页,只不过题意有一些细微偏差,但是不影响本题结论的正确性,做法可以看:洛谷P2398。我们只需要进行一次预处理,下底分块,保留SQRT(n)的查询就行了。虽然时间上Vjudge垫底,但是毕竟我弱啊……,下面是一段代码。#include<cstdio> #include<algorithm> using namespace std; const int maxn = 4e6 + 5; long long f[maxn]; int&n
? 解题记录 ? ? 洛谷 ? ? 筛法 ?    2017-09-14 12:00:40    230    0    0
题目描述for i=1 to n for j=1 to n  sum+=gcd(i,j)给出n求sum. gcd(x,y)表示x,y的最大公约数. 输入输出格式输入格式:   n   输出格式:   sum   输入输出样例输入样例#1:2 输出样例#1:5 说明数据范围 30% n<=3000 60% 7000<=n<=7100 100% n<=100000 题目十分奇特,我们知道1e6的数据n^2 log n 卡不死你也能卡爆你。我们需要将复杂度控制在O(n log n)以内。我们这样想,首先这些GCD可以被重新分
? 解题记录 ? ? 洛谷 ? ? 筛法 ?    2017-09-09 20:52:39    375    0    0
题目背景题目名称是吸引你点进来的 实际上该题还是很水的 题目描述区间质数个数 输入输出格式输入格式:   一行两个整数 询问次数n,范围m 接下来n行,每行两个整数 l,r 表示区间   输出格式:   对于每次询问输出个数 t,如l或r∉[1,m]输出 Crossing the line   输入输出样例输入样例#1:2 5 1 3 2 6 输出样例#1:2 Crossing the line 说明【数据范围和约定】 对于20%的数据 1<=n<=10 1<=m<=10 对于100%的数据 1<=n<=1000 1
? 解题记录 ? ? 洛谷 ? ? 欧拉函数 ? ? 筛法 ?    2017-08-22 11:23:59    309    0    0
题目描述作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。 输入输出格式输入格式:  共一个数N   输出格式:  共一个数,即C君应看到的学生人数。   输入输出样例输入样例#1:4 输出样例#1:9 说明【数据规模和约定】 对于 100% 的数据,1 ≤ N ≤ 40000 考虑对于一个矩形,站在左下角如何才能看到右上角的人?不难发现,如果有遮挡