生活随笔
收集整理的這篇文章主要介紹了
HDU6428-Calculate-数论函数
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
并不知道為什么同樣一份代碼早上超時下午就A了…好像數據是隨機的?
做的第一道不是簡單板題的數論函數題.果然做不出來…
在網上研究了好久,才算稍微研究明白.看到了兩種推導的思路.(寫了半天發現講起來好麻煩,有時間再來更新)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<set>
#include<vector>using namespace std
;typedef long long ll
;
const int MAXN
=1e7+5;int prime
[MAXN
],h
[MAXN
],f2
[MAXN
],f3
[MAXN
],deg
[MAXN
],last
[MAXN
];
bool check
[MAXN
]; int tot
;void pre()
{h
[1]=f2
[1]=f3
[1]=last
[1]=1; tot
=0;for(int i
=2;i
<MAXN
;i
++){if(!check
[i
]){prime
[tot
++]=i
; h
[i
]=i
-2; f2
[i
]=f3
[i
]=i
; last
[i
]=1; deg
[i
]=1;}for(int j
=0;j
<tot
&& (ll
)prime
[j
]*i
<(ll
)MAXN
;j
++){int x
=prime
[j
]*i
; check
[x
]=true;if(i
%prime
[j
]){h
[x
]=h
[i
]*(prime
[j
]-2); f2
[x
]=f2
[i
]*prime
[j
]; f3
[x
]=f3
[i
]*prime
[j
];last
[x
]=i
; deg
[x
]=1;}else{last
[x
]=last
[i
]; deg
[x
]=deg
[i
]+1;if(last
[x
]>1) {h
[x
]=h
[x
/last
[x
]]*h
[last
[x
]];}else {if(i
>prime
[j
]) h
[x
]=h
[i
]*prime
[j
];else h
[x
]=(prime
[j
]-1)*(prime
[j
]-1);}f2
[x
]=f2
[i
]*(deg
[x
]%2==1?prime
[j
]:1);f3
[x
]=f3
[i
]*(deg
[x
]%3==1?prime
[j
]:1);break;}}}
}const int mod
=1<<30;
int A
,B
,C
;ll
Min(ll A
,ll B
,ll C
)
{ll ret
=A
;if(B
<ret
&& B
*B
<ret
) ret
=B
*B
;if(C
<ret
&& C
*C
<ret
&& C
*C
*C
<ret
) ret
=C
*C
*C
;return ret
;
}int main()
{pre();int T
;scanf("%d",&T
);while(T
--){ll ans
=0;scanf("%d%d%d",&A
,&B
,&C
);int limit
=Min(A
,B
,C
);for(int i
=1;i
<=limit
;i
++){ans
=ans
+(ll
)h
[i
]*((A
/i
)*(B
/f2
[i
])*(C
/f3
[i
])); }printf("%lld\n",ans
%mod
);}return 0;
}
總結
以上是生活随笔為你收集整理的HDU6428-Calculate-数论函数的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
