首页 > 代码库 > [BZOJ2005][NOI2010]能量采集
[BZOJ2005][NOI2010]能量采集
听小乐乐的去做NOI了~\(≧▽≦)/~啦啦啦
一开始sha bi了,没考虑2,3->4,6。。。样例骗人QAQ
容易得到答案就是∑i(1<=i<=n)∑j(1<=j<=m)gcd(i,j)*2-1
但暴力是nm的,GG
我们转换一下思路,设f[i]为gcd为i的点对个数,怎么求f[i]呢?直接算好像并不行,考虑容斥,显然(n/i)*(m/i)就是有公因数为i的点对个数,然后减去f[2*i],f[3*i]...就好了
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<iostream> #include<string> #include<ctime> #include<queue> #include<map> #include<set> #include<vector> typedef long long LL; using namespace std; const int N=100010; LL n,m,k,ans,f[N]; LL read() {LL d=0,f=1; char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1; c=getchar();} while (c>=‘0‘&&c<=‘9‘) d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;} void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);} int main() { //judge(); n=read(); m=read(); int ljj=max(n,m),pjy=min(n,m); for (int i=ljj;i>=1;i--) { f[i]=(n/i)*(m/i); for (int j=2*i;j<=pjy;j+=i) f[i]-=f[j]; } for (LL i=1;i<=ljj;i++) ans+=f[i]*(2*i-1); printf("%lld",ans); return 0; }
[BZOJ2005][NOI2010]能量采集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。