欧拉函数板子题

Visible Lattice Points

分析：

• 让求有多少对 ( x , y ) (x,y) (x,y) 使得 g c d ( x , y ) = 1 gcd(x,y)=1 gcd(x,y)=1 , 现考虑有多少 x x x 与y互质 ( x < y ) (x<y) (x<y) , 即求 φ ( y ) \varphi(y) φ(y) , 总的： a n s = 3 + 2 ∑ i = 2 n φ ( i ) ans=3+2\sum_{i=2}^n\varphi(i) ans=3+2∑i=2n​φ(i) , 3 3 3 个单独拎出来是 ( 1 , 0 ) ( 0 , 1 ) ( 1 , 1 ) (1,0)(0,1)(1,1) (1,0)(0,1)(1,1)

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int phi[N],s[N];
void euler(int n)
{
    for(int i=1;i<=n;i++) phi[i]=i;
    for(int i=2;i<=n;i++)
    {
        if(phi[i]==i)
        {
            for(int j=i;j<=n;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
    for(int i=2;i<=n;i++) s[i]=s[i-1]+phi[i];
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    euler(1005);
    int T;
    cin>>T;
    int cnt=0;
    while(T--)
    {
        int n;
        cin>>n;
        cout<<++cnt<<' '<<n<<' '<<3+2*s[n]<<endl;
    }

    return 0;
}

同余方程

#include <bits/stdc++.h>
#define int long long 
using namespace std;

int euler(int x)//欧拉函数
{
	int ans=x;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			ans=ans-ans/i;
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ans=ans-ans/x;
	return ans;
}
int ksm(int a,int b,int p)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p; b >>= 1;
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a,b;
    cin>>a>>b;
    int ans=ksm(a,euler(b)-1,b);
    cout<<ans<<endl;
	return 0;
}