题目链接:HDOJ - 5212
题目分析
首先的思路是,考虑每个数对最终答案的贡献。
那么我们就要求出:对于每个数,以它为 gcd 的数对有多少对。
显然,对于一个数 x ,以它为 gcd 的两个数一定都是 x 的倍数。如果 x 的倍数在数列中有 k 个,那么最多有 k^2 对数的 gcd 是 x 。
同样显然的是,对于两个数,如果他们都是 x 的倍数,那么他们的 gcd 一定也是 x 的倍数。
所以,我们求出 x 的倍数在数列中有 k 个,然后就有 k^2 对数满足两个数都是 x 的倍数,这 k^2 对数的 gcd,要么是 x ,要么是 2x, 3x, 4x...
并且,一个数是 x 的倍数的倍数,它就一定是 x 的倍数。所以以 x 的倍数为 gcd 的数对,一定都包含在这 k^2 对数中。
如果我们从大到小枚举 x ,这样计算 x 的贡献时,x 的多倍数就已经计算完了。我们用 f(x) 表示以 x 为 gcd 的数对个数。
那么 f(x) = k^2 - f(2x) - f(3x) - f(4x) ... f(tx) (tx <= 10000, k = Cnt[x])
这样枚举每个 x ,然后枚举每个 x 的倍数,复杂度是用调和级数计算的,约为 O(n logn)。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue> using namespace std; typedef long long LL;
typedef unsigned long long ULL;
typedef double LF; inline int gmin(int a, int b) {return a < b ? a : b;}
inline int gmax(int a, int b) {return a > b ? a : b;} inline LF gmin(LF a, LF b) {return a < b ? a : b;}
inline LF gmax(LF a, LF b) {return a > b ? a : b;} const LF Eps = 1e-8; inline LF Sqr(LF x) {return x * x;} inline int Sgn(LF x)
{
if (x < -Eps) return -1;
if (x > Eps) return 1;
return 0;
} const int MaxN = 10000 + 5, Mod = 10007; int n, Ans, Num, Temp, SqrtX;
int Cnt[MaxN], f[MaxN], Pos[MaxN]; int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = 1; i <= 10000; ++i) Cnt[i] = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &Num);
SqrtX = (int)sqrt((LF)Num);
for (int j = 1; j <= SqrtX; ++j)
{
if (Num % j != 0) continue;
++Cnt[j];
if (Num / j != j) ++Cnt[Num / j];
}
}
Ans = 0;
for (int i = 10000; i >= 1; --i)
{
f[i] = Cnt[i] * Cnt[i] % Mod;
for (int j = i * 2; j <= 10000; j += i)
f[i] = (f[i] - f[j] + Mod) % Mod;
Temp = i * (i - 1) % Mod;
Ans = (Ans + f[i] * Temp % Mod) % Mod;
}
printf("%d\n", Ans);
}
return 0;
}
[HDOJ 5212] [BestCoder Round#39] Code 【0.0】的更多相关文章
-
暴力+降复杂度 BestCoder Round #39 1002 Mutiple
题目传送门 /* 设一个b[]来保存每一个a[]的质因数的id,从后往前每一次更新质因数的id, 若没有,默认加0,nlogn复杂度: 我用暴力竟然水过去了:) */ #include <cst ...
-
贪心 BestCoder Round #39 1001 Delete
题目传送门 /* 贪心水题:找出出现次数>1的次数和res,如果要减去的比res小,那么总的不同的数字tot不会少: 否则再在tot里减去多余的即为答案 用set容器也可以做,思路一样 */ # ...
-
SpringBoot2整合Shiro报错 UnavailableSecurityManagerException: No SecurityManager accessible to the calling code 【已解决】
SpringBoot集成Shiro报错 UnavailableSecurityManagerException: No SecurityManager accessible to the callin ...
-
【CS Round #39 (Div. 2 only) D】Seven-segment Display
[Link]:https://csacademy.com/contest/round-39/task/seven-segment-display/ [Description] 0..9各自有一个数字, ...
-
【CS Round #39 (Div. 2 only) C】Reconstruct Sum
[Link]:https://csacademy.com/contest/round-39/task/reconstruct-sum/ [Description] 给你一个数字S; 让你找有多少对A, ...
-
【CS Round #39 (Div. 2 only) B】Circle Elimination
[Link]:https://csacademy.com/contest/round-39/task/circle-elimination/ [Description] [Solution] 把n个点 ...
-
【CS Round #39 (Div. 2 only) A】Removed Pages
[Link]: [Description] [Solution] 每读入一个x; 把a[(x-1)/2]置为1即可; 统计1的个数 [NumberOf WA] [Reviw] [Code] /* */ ...
-
[BestCoder Round#26] Apple 【组合数学】
题目链接:HDOJ - 5160 题目分析 第一眼看上去,要求统计所有不同排列对答案的贡献.嗯...完全没有想法. 但是,如果我们对每个数字单独考虑,计算这个数字在总答案中的贡献,就容易多了. 对于一 ...
-
hdu 1047 (big integer sum, fgets or scanf, make you func return useful infos) 分类: hdoj 2015-06-18 08:21 39人阅读 评论(0) 收藏
errors made, boundary conditions, <= vs < , decreasing vs increasing , ++, –, '0'/'1' vs 0/1 p ...
随机推荐
-
T-SQL 转义select … like中的特殊字符(百分号)
众所周知,T-SQL中LIKE运算符使用%符号表示通配符.很多时候可能需要查询包含有%的数据,比如需要查询字段coupon中含有5%的数据.那么如何使用已经有百分号(%)符号的LIKE搜索字符串呢? ...
-
在线浏览pdf文件,pdfobject的简单使用
该js插件,官网有详细的使用教程(网址:http://www.pdfobject.com/examples/).打开里面的例子后,查看新打开页面,打开并查看该页面的源代码. 需要的材料: 1.PDFo ...
-
twisted学习笔记4 部署Twisted 应用程序
原创博文,转载请注明出处. Twisted是一个可扩展,跨平台的网络服务器和客户端引擎. Twisted Application 框架有五个主要基础部分组成:服务,应用程序,TAC文件插件和twist ...
-
Codeforces 1032 - A/B/C/D/E - (Undone)
链接:http://codeforces.com/contest/1032/ 是真的真的真的忍不住想吐槽这题意是真的真的真的读不懂…… A - Kitchen Utensils - [简单数学题] 题 ...
-
h5 中的 section 标签
转自 http://www.studyofnet.com/news/331.html 本文导读:<section> 标签定义文档中的节(section.区段).比如章节.页眉.页脚或文档中 ...
-
Linux 下查看某个进程运行的堆栈信息
1. 根据进程名称查询进程ID ps -ef | grep processName 2. 将进程的堆栈信息写入log gstack processId > s.log 3. 查看log vim ...
-
mongodb-添加或删除字段
1 .添加一个字段. url 代表表名 , 添加字段 content. 字符串类型. db.url.update({}, {$set: {content:""}}, {multi ...
-
js阻止表单提交
<!DOCTYPE html><html><head> <title>Simple Login Form</title> < ...
-
mysqlbinlog用法总结
通过binlog日志统计dml语句,找出操作频繁的表 mysqlbinlog --no-defaults --base64-output=decode-rows -v -v mysql-bin.0 ...
-
Linux编程之错误代码
头文件/usr/include/asm-generic/errno-base.h定义错误码: #ifndef _ASM_GENERIC_ERRNO_BASE_H #define _ASM_GENERI ...