锐客网

  1. 首页 > it技术 > >

数学推导|HDU-5528-Count a * b-2015长春B题(数学推导)

数论数学推导

题目链接
题意:给定一个n，求 g(n)g(n)=f(x1)+f(x2)...+f(xm) ,其中 xi是 n 的约数， f(n)是取(a，b)，a 思路：进行公式推导把。
f(x)=∑x?1a=0∑x?1b=0[x?a?b]=x2?∑x?1a=0∑x?1b=0[x∣a?b]=x2?∑x?1a=0∑x?1b=0[xgcd(x,a)∣agcd(x,a)?b]
这里b只能取x的倍数，所以公式可以化简为
=x2?∑x?1a=0xxgcd(x,a)=x2?∑x?1a=0gcd(x,a)==x2?∑d|xd?euler(x/d)
g(n)=∑x|nf(x)=∑x|nx2?∑d|xd?euler(x/d)=∑x|nx2?∑x|n∑d|xd?euler(xd)转化一下=∑x|nx2?∑d|n∑i|ndd?euler(i)=∑x|nx2?∑d|nd?∑i|ndeuler(i)根据一个性质：一个数的约数的欧拉函数和还为这个数原式可化简为=∑x|nx2?∑dnd?nd=∑x|nx2?∑d|nn=∑x|nx2?∑x|nx2?n?h(n)（其中h(n)是n约数的个数）
最后由于积性函数的性质
g(n)=∏i=1r(pai+1i)2?1p2i?1?n?∏i=1rai+1

#include using namespace std; #define maxn 100010 #define ull unsigned long long bool vis[maxn]; int prime[maxn]; int tp=0; void init(void) { memset(vis,0,sizeof vis); vis[1]=vis[0]=1; for(int i=1; i1) { ss*=2; ans*=(1+(ull)n*(ull)n); } //cout << ans << " " << ss << endl; printf("%llu\n",ans-ss); } int main() { init(); int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); sov(n); } return 0; }

    推荐阅读


    上一篇：Android|Android 如何远端调试framework和APK（）

    下一篇：韦根协议 wiegand