[HDOJ 5212] [BestCoder Round#39] Code 【0.0】

时间:2023-02-26 18:17:18

题目链接: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】的更多相关文章

  1. 暴力&plus;降复杂度 BestCoder Round &num;39 1002 Mutiple

    题目传送门 /* 设一个b[]来保存每一个a[]的质因数的id,从后往前每一次更新质因数的id, 若没有,默认加0,nlogn复杂度: 我用暴力竟然水过去了:) */ #include <cst ...

  2. 贪心 BestCoder Round &num;39 1001 Delete

    题目传送门 /* 贪心水题:找出出现次数>1的次数和res,如果要减去的比res小,那么总的不同的数字tot不会少: 否则再在tot里减去多余的即为答案 用set容器也可以做,思路一样 */ # ...

  3. SpringBoot2整合Shiro报错 UnavailableSecurityManagerException&colon; No SecurityManager accessible to the calling code 【已解决】

    SpringBoot集成Shiro报错 UnavailableSecurityManagerException: No SecurityManager accessible to the callin ...

  4. 【CS Round &num;39 &lpar;Div&period; 2 only&rpar; D】Seven-segment Display

    [Link]:https://csacademy.com/contest/round-39/task/seven-segment-display/ [Description] 0..9各自有一个数字, ...

  5. 【CS Round &num;39 &lpar;Div&period; 2 only&rpar; C】Reconstruct Sum

    [Link]:https://csacademy.com/contest/round-39/task/reconstruct-sum/ [Description] 给你一个数字S; 让你找有多少对A, ...

  6. 【CS Round &num;39 &lpar;Div&period; 2 only&rpar; B】Circle Elimination

    [Link]:https://csacademy.com/contest/round-39/task/circle-elimination/ [Description] [Solution] 把n个点 ...

  7. 【CS Round &num;39 &lpar;Div&period; 2 only&rpar; A】Removed Pages

    [Link]: [Description] [Solution] 每读入一个x; 把a[(x-1)/2]置为1即可; 统计1的个数 [NumberOf WA] [Reviw] [Code] /* */ ...

  8. &lbrack;BestCoder Round&num;26&rsqb; Apple 【组合数学】

    题目链接:HDOJ - 5160 题目分析 第一眼看上去,要求统计所有不同排列对答案的贡献.嗯...完全没有想法. 但是,如果我们对每个数字单独考虑,计算这个数字在总答案中的贡献,就容易多了. 对于一 ...

  9. hdu 1047 &lpar;big integer sum&comma; fgets or scanf&comma; make you func return useful infos&rpar; 分类: hdoj 2015-06-18 08&colon;21 39人阅读 评论&lpar;0&rpar; 收藏

    errors made, boundary conditions, <= vs < , decreasing vs increasing , ++, –, '0'/'1' vs 0/1 p ...

随机推荐

  1. T-SQL 转义select … like中的特殊字符&lpar;百分号&rpar;

    众所周知,T-SQL中LIKE运算符使用%符号表示通配符.很多时候可能需要查询包含有%的数据,比如需要查询字段coupon中含有5%的数据.那么如何使用已经有百分号(%)符号的LIKE搜索字符串呢? ...

  2. 在线浏览pdf文件,pdfobject的简单使用

    该js插件,官网有详细的使用教程(网址:http://www.pdfobject.com/examples/).打开里面的例子后,查看新打开页面,打开并查看该页面的源代码. 需要的材料: 1.PDFo ...

  3. twisted学习笔记4 部署Twisted 应用程序

    原创博文,转载请注明出处. Twisted是一个可扩展,跨平台的网络服务器和客户端引擎. Twisted Application 框架有五个主要基础部分组成:服务,应用程序,TAC文件插件和twist ...

  4. Codeforces 1032 - A&sol;B&sol;C&sol;D&sol;E - &lpar;Undone&rpar;

    链接:http://codeforces.com/contest/1032/ 是真的真的真的忍不住想吐槽这题意是真的真的真的读不懂…… A - Kitchen Utensils - [简单数学题] 题 ...

  5. h5 中的 section 标签

    转自 http://www.studyofnet.com/news/331.html 本文导读:<section> 标签定义文档中的节(section.区段).比如章节.页眉.页脚或文档中 ...

  6. Linux 下查看某个进程运行的堆栈信息

    1. 根据进程名称查询进程ID ps -ef | grep processName 2. 将进程的堆栈信息写入log gstack processId > s.log 3. 查看log vim ...

  7. mongodb-添加或删除字段

    1 .添加一个字段.  url 代表表名 , 添加字段 content. 字符串类型. db.url.update({}, {$set: {content:""}}, {multi ...

  8. js阻止表单提交

    <!DOCTYPE html><html><head>    <title>Simple Login Form</title>    &lt ...

  9. mysqlbinlog用法总结

    通过binlog日志统计dml语句,找出操作频繁的表 mysqlbinlog --no-defaults --base64-output=decode-rows -v -v   mysql-bin.0 ...

  10. Linux编程之错误代码

    头文件/usr/include/asm-generic/errno-base.h定义错误码: #ifndef _ASM_GENERIC_ERRNO_BASE_H #define _ASM_GENERI ...