Description
令f(m)=| { (a,b) | a * b % m != 0，0<=a< m，0<=b< m } |，求
文章图片
Input
第一行为一整数T表示用例组数，每组用例占一行为一整数n
（1<=T<=20000，1<=n<=10^9）
Output
对于每组用例，输出g(n)，结果模2^64
Sample Input
2
6
514
Sample Output
26
328194
Solution
令h(m)=|{(a,b)|a*b%m=0,0<=a< m,0<=b< m}|，则
文章图片
问题转化为求n的因子数以及因子平方和，而这两个都是积性函数，对n一遍素因子分解即可得到答案
文章图片
Code
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 33333
typedef long long ll;
typedef unsigned long long ull;
typedef pair P;
vector【HDU|HDU 5528 Count a * b（积性函数）】vec;
int prime[maxn],is_prime[maxn],res;
void get_prime(int n)
{
res=0;
memset(is_prime,0,sizeof(is_prime));
for(int i=2;
i1)vec.push_back(make_pair(n,1));
}
void solve(int n)
{
ull ans1=1,ans2=1;
for(int i=0;
i 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- hdu|2016 Multi-University Training Contest 1 C Game(hdu 5725)
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- HDU|HDU 1576 A/B（拓展欧几里得，模板题）