BZOJ2005: [Noi2010]能量采集(容斥原理 莫比乌斯…
2018-07-09 13:25:10来源:博客园 阅读 ()
Submit: 4727 Solved: 2877
[Submit][Status][Discuss]
Description
Input
仅包含一行,为两个整数n和m。
Output
仅包含一个整数,表示总共产生的能量损失。
Sample Input
5 4
【样例输入2】
3 4
Sample Output
36
【样例输出2】
20
对于100%的数据:1 ≤ n, m ≤ 100,000。
HINT
Source
第二道自己做出来的NOI系列的数学题(雾)
首先$ans = \sum_{i = 1}^N \sum_{j = 1}^M 2 * (gcd(i, j) - 1) + 1$
化简得到$ans = 2 * \sum_{i = 1}^N \sum_{j = 1}^M gcd(i, j) - N * M$
然后就是怎么求GCD啦。这个问题我记得去年的时候遇到过,不过那时候还比较naive不会做
今天重新来想其实还是挺简单的。
利用容斥原理,$gcd(i,j)$对答案的贡献=所有含有$gcd(i,j)$因子的数对 - 不是以$gcd(i, j)$为最大因子的数对
前面那个是$\frac{N}{gcd(i, j)} * \frac{M}{gcd(i, j)}$
后面的可以容斥计算,这里必须要倒着算不然容斥起来很麻烦。。
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> #define int long long const int INF = 1e9 + 10, MAXN = 2 * 1e5 + 10; using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; long long num[MAXN];//以i为最大公约数的数有多少个 long long GetGcd() { long long ans = 0; if(N > M) swap(N, M); for(int i = N; i >= 1; i--) { long long rt = 0; rt += (N / i) * (M / i); for(int j = i << 1; j <= N; j += i) rt -= num[j]; num[i] = rt; ans += num[i] * i; } return ans; } main() { #ifdef WIN32 // freopen("a.in", "r", stdin); #endif N = read(); M =N; long long ans = 0; ans = GetGcd(); printf("%lld", ans); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P3205 [HNOI2010]合唱队 2019-08-26
- NOI2010 超级钢琴 2018-06-27
- bzoj2006 [ NOI2010 ] && bzoj3784 --点分 2018-06-17
- bzoj2002 [ HNOI2010 ] -- LCT 2018-06-17
- P1063 能量项链 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash