Mathematical knowledge (Euler function)

Premise ： Euler function Φ（n） Express 1~n China and n The number of Coprime numbers .

 【 If there are only two numbers 1 A common qualitative factor , Called coprime 】

eg：ϕ（6）=2.[1,2,3,4,5,6]

How to ask for 1~n China and n The number of Coprime numbers ？

From the basic theorem of arithmetic , Any number n It can be expressed by the following formula , among Pi It's the prime factor ,ai Is the index .

 

 

Here we will also introduce the principle of inclusion and exclusion ：

Since we need to calculate the number of Coprime numbers , Then delete all multiples of prime factors , The operation is as follows ：

1） from 1~n Subtract from p1,p2,…,pk Multiple 【- p. 】

2） Add all the pi*pj Multiple              【+ accidentally 】

3） Subtract all pi*pj*pk Multiple            【- p. 】

So ：

  Simplify to ：

  Explanation of supplementary steps ：

 

 

		1	2	3	4	5	6	7
First step ：	Delete Pi Multiple	-1			-1	-1	-1
	Delete Pj Multiple		-1		-1	-1		-1
	Delete pk Multiple			-1		-1	-1	-1
The second step ：	add pi*pj Multiple				+1	+1
	add pi*pk Multiple					+1	+1
	add pj*pk Multiple					+1		+1
The third step ：	subtract pi*pj*pk Multiple					-1
in total		-1	-1	-1	-1	-1	-1	-1

Topic link ：873. Euler function - AcWing Question bank

Topic ：

  The following code to solve the prime factor can refer to this blog ：

Mathematical problems （ number theory ） Try division to judge prime numbers 、 Decomposing prime factor , Sieve prime number _ Wu Yu 4 The blog of -CSDN Blog https://blog.csdn.net/WSY444/article/details/125496621?spm=1001.2014.3001.5502

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll t,n;
int main()
{
    cin>>t;
   while(t--)
   {
       cin>>n;
       ll ans=n;
       for(int i=2;i<=n/i;i++)
       {
           if(n%i==0)
           {
               ans=ans/i*(i-1);// Equivalent to ans*(1-1/i)
               while(n%i==0) n/=i;
           }
       }
       if(n>1) ans=ans/n*(n-1);
       cout<<ans<<endl;
   }
    return 0;
}