用递归计算一个组合数学方面的问题,怎么实现的C语言方法

Problem Description
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 m, 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 n. Your task is to find g(n) modulo 264.

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 n.

1≤T≤20000
1≤n≤109

Output
For each test case, print one integer s, representing g(n) modulo 264.

Sample Input
2
6
514

Sample Output
26
328194

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题