小学生在上课
| 总时限 | 11s | 内存限制 | 256MB |
|---|---|---|---|
| 出题人 | jzc | 提交情况 | 66/277 |
| 初始分值 | 600 | 锁定情况 |
背景
小学生在学校上数学课……
描述
数学课上，小学生刚学会了乘除法。老师问了他们一系列这样的问题：给一个正整数N，答案要为小于N的正整数，比如N = 4，
老师会问：1乘以几除以4余1？
小学生回答：1！
老师继续问：2乘以几除以4余1？
小学生回答：没有！
老师继续问：3乘以几除以4余1？
小学生回答：3！
LJ是众小学生之一，他觉得这个问题太简单了，于是就想，对于一个N，如果老师从1 问到 N-1（乘以几除以N余1 ），那么所有答案的和是多少，如果答案是”没有”则认为答案是0。
输入格式
一个整数 T，表示数据组数
之后的T行，每行一个整数N
输出格式
共T行，每行一个整数，表示和
样例输入
1
4
样例输出
4
数据范围与约定
2 <= N <= 1000000000，T <= 10。
单点时间限制1s。
来源
原创
首先，a在mod p 的意义下有逆元，当且仅当gcd(a,p)=1
另外,若a^-1=b (mod p) 则 b^-1=a (mod p) ,故a^-1+b^-1=a+b (mod p)
然后n以内所有gcd(n,i)=1的i的和=n*phi(n)/2 //完全积性的定理
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
typedef long long ll;
int T;
ll n;
int main()
{
// freopen(".in","r",stdin);
cin>>T;
while(T--)
{
cin>>n;
ll ans=n;
Fork(i,2,sqrt(n))
{
if (n%i==0)
{
ans*=i-1,n/=i;
while (n%i==0) ans*=i,n/=i;
}
}
if (n>1) ans*=n-1;
ans/=2;
cout<<ans<<endl; } return 0;
}