shunfurh
编程介的小学生
2019-01-02 23:47

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

  • Golang
  • r语言
  • erlang

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条回答