CH BR8(小學生在上課-逆元和互質數一一對應關系)

小學生在上課
總時限 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;
}