题目来源：能力提升综合题单Part6 数学1
(Exgcd)
求解形如下的不定方程
关于该方程的性质
(1°)首先若方程有解则，(gcd(a,b)mid c)，否则无解
(2°)求得一组特解(x^ {'},y^{'})，那么其通解形如
(3°)
(x)最小值为(x^{'} mod frac{b}{gcd(a,b)})
(y)最小值为(y^{'}modfrac{a}{gcd(a,b)})
注意在实际中(Exgcd)并不能处理(a,b)为负数的情况
常用手段是按题意取相反数
青蛙的约会
推一波式子就会发现
问题转化为求解
(q)的最小正整数解
直接套用(Exgcd)就基本可以解决问题了
有一个小细节需要注意一下
若(l)或(n-m)为负数时，需要将(n-m)和(x-y)取一下相反数来解决问题
Code
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
template<typename _T>
void read(_T &x)
{
x=0;char s=getchar();int f=1;
while('0'>s||s>'9'){f=1;if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=f;
}
inline int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
inline void Exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1ll;y= 0;
return;
}
Exgcd(b,a%b,x,y);
int t = x;
x=y;
y=t-(a/b)*y;
}
signed main()
{
int x,y,m,n,l;
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
read(x);
read(y);
read(m);
read(n);
read(l);
int xx,yy,num;
int a,b,c;
a= l,b=n-m,c=(x-y);
if(b < 0)
{
c=-c;
b=-b;
}
num = gcd(a,b);
if(c%num != 0)
{
cout<<"Impossible";
return 0;
}
Exgcd(b,a,xx,yy);
xx*=c/num;
yy*=c/num;
cout<<((xx)%(a/num)+(a/num))%(a/num);
}
欧拉函数(phi)
欧拉函数线筛
先来一发线筛
inline void prime_phi(int n)
{
phi[1] =1;
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
prime[++st] = i;
phi[i] = i-1;
vis[i] = i;
}
for(int j=1;j<=st;j++)
{
if(prime[j] > vis[i] || i*prime[j] > n) break;
vis[i*prime[j]] = prime[j];
if(i%prime[j]==0)
phi[i*prime[j]] = phi[i] * prime[j];
else phi[i*prime[j]] = phi[i]*(prime[j]-1);
}
}
}
线筛写错了就等着崩盘吧
欧拉函数性质
欧拉函数多用于求解与互质相关的题目
若在(N)的算术基本定理中(N=p_{1}^{c_1} p_{2}^{c_2}…p_{m}^{c_m})
那么有
(1.)若(a,b)互质，则(phi(ab)=phi(a)phi(b))
该性质说明了欧拉函数为积性函数
(2.)若(p)为素数若(pmid n)且(p^2mid n)，则(phi(n)=phi(frac{n}{p}) imes p)
(3.)若(p)为素数若(pmid n)且(p^2
mid n)，则(phi(n)=phi(frac{n}{p}) imes (p-1))
(4.) (sum_{dmid n}phi(i)=n)
GCD SUM
原式要求
考虑对每一个(gcd(i,j))
假如其不为(1)
设为(gcd(i,j)=p)
其贡献可以转化为(gcd(frac{i}{p},frac{j}{p}) imes p)
所以问题就被转化为了对一个数(frac{i}{p}求phi(frac{i}{p}) imes p)
这样(gcd(i,j)=p)的贡献就可以在(frac{i}{p},frac{j}{p})时被算出来
那么原式可以化为
这个东西显然可以前缀和求解
有些小细节需要注意：
算出来的结果需要再乘2，然后容斥一下就好了
Code
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
const int p=1e6+5;
template<typename _T>
void read(_T &x)
{
x=0;char s=getchar();int f=1;
while('0'>s||s>'9'){f=1;if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=f;
}
inline int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int vis[p];
int prime[p];
int phi[p];
int st;
int n;
inline void prime_phi(int n)
{
phi[1] =1;
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
prime[++st] = i;
phi[i] = i-1;
vis[i] = i;
}
for(int j=1;j<=st;j++)
{
if(prime[j] > vis[i] || i*prime[j] > n) break;
vis[i*prime[j]] = prime[j];
if(i%prime[j]==0)
phi[i*prime[j]] = phi[i] * prime[j];
else phi[i*prime[j]] = phi[i]*(prime[j]-1);
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
read(n);
prime_phi(n);
int sum = 0;
for(int i=1;i<=n;i++)
for(int p=1;p<=n/i;p++)
{
sum+=phi[i]*p;
}
sum*=2;
for(int i=1;i<=n;i++)
{
sum-=i;
}
cout<<sum;
}