题目链接https://cn.vjudge.net/problem/HDU-5528
Marry likes to count the number of ways to choose two non-negative integers a and b less than m to make a×b mod m≠0.
Let's denote f(m)as the number of ways to choose two non-negative integers a and b less than m to make a×b mod m≠0.
She has calculated a lot of f(m) for different mm, and now she is interested in another function g(n)=∑m|nf(m). For example, g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26. She needs you to double check the answer.
Give you nn. Your task is to find g(n) modulo 2^64.
Input
The first line contains an integer T indicating the total number of test cases. Each test case is a line with a positive integer nn.
1≤T≤20000
1≤n≤10^9
Output
【hdu5528Count a * b（数论）】For each test case, print one integer ss, representing g(n) modulo 2^64.
Sample Input
2 6 514
Sample Output
26 328194
听说结果没有大于等于2^64的，直接用long long算？？？
推导见大神博客https://blog.csdn.net/Coldfresh/article/details/82189233
#include
#include
#include
#include
#include
#include
#include 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] 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
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally