首页 > 代码库 > HDU 4944 FSF’s game(计数游戏)
HDU 4944 FSF’s game(计数游戏)
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4944
题意:
给定一个长度n, 用长度为 a,b 的边组成一个矩形 (1<=a<=b<=n) 我们可以将其组成n(n+1)/2个不同的矩形,
对于每一个矩形 我们可以得到一个val val=sigma(a*b/gcd(a/k,b/k)) 其中k为a,b的公因子,求这个val;
分析:
我们定义一个函数calu(i,j) calu(i,j)的意思是sigma{(i*j/gcd(i/k,j/k))},
则ans=sigma {calu(i,j)}(1<=i<=j<=n);
我们设dp[n]表示最大的边长为n的边所得到的val,
那么dp[n]=dp[n-1]+sigma{ calu(i,n) }(1<=i<=n)
然后我们需要解决的问题就是求sigma{ calu(i,n) }(1<=i<=n);
我们先讨论calu(i,n)=n*(i/c1+i/c2+...),其中cj为n和i的最大公约数d的所有因子。
那么我们可以枚举所有n的因子j,对于因子j,存在这个因子且小于等于n的数字中有j,2*j,3*j,...,n。
我们可以得到s[j]=(1+2+3+...n/j)*n=(n/j+1)*(n/j)/2*n。
那么val[n]=sigma{fun(i,n)}(1<=i<=n)=sigma{s[j]} (j为n的因子)。
代码如下:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const LL mod = (LL)1<<32; const int maxn = 500010; LL cnt[maxn],dp[maxn]; void init() { memset(cnt,0,sizeof(cnt)); for(LL i=1;i<maxn;i++){//枚举因子 for(LL j=i;j<maxn;j+=i)//统计因子的个数的和 cnt[j]+=(j/i+1)*(j/i)/2; } } void solve() { dp[1]=1; for(int i=2;i<maxn;i++){ dp[i]=(dp[i-1]+i*cnt[i])%mod; } } int main() { int t,n,cas=1; init(); solve(); scanf("%d",&t); while(t--){ scanf("%d",&n); printf("Case #%d: %I64d\n",cas++,dp[n]); } return 0; }
HDU 4944 FSF’s game(计数游戏)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。