CH BR8(小学生在上课-逆元和互质数一一对应关系)

2022-12-23 07:51:02

小学生在上课

总时限	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

样例输出

数据范围与约定

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;

}

码农公寓