数学
(试除法判定质数)
#include<iostream>
#include<algorithm>
using namespace std;
bool is_Prime(int x)
{
if(x<2) return false;
for(int i=2;i<=x/i;i++)
if(x%i==0) return false;
return true;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
if(is_Prime(x)) puts("Yes");
else puts("No");
}
return 0;
}
(分解质因数)
#include<iostream>
#include<algorithm>
using namespace std;
void divide(int x)
{
for(int i=2;i<=x/i;i++)
if(x%i==0)
{
int s=0;
while(x%i==0) x/=i,s++;
cout<<i<<" "<<s<<endl;
}
if(x>1) cout<<x<<" 1"<<endl;
cout<<endl;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
divide(x);
}
return 0;
}
(筛质数)
#include<iostream>
using namespace std;
const int N=1000010;
int primes[N];
bool st[N];
int cnt;
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(st[i]) continue;
primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i)
st[j]=true;
}
}
int main()
{
int n;
cin>>n;
get_primes(n);
cout<<cnt<<endl;
return 0;
}
(试除法求约数)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> get_divisors(int x)
{
vector<int> res;
for(int i=1;i<=x/i;i++)
if(x%i==0)
{
res.push_back(i);
if(i!=x/i) res.push_back(x/i);
}
sort(res.begin(),res.end());
return res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
auto ans=get_divisors(x);
for(auto& a:ans) cout<<a<<" ";
cout<<endl;
}
return 0;
}
(约数个数)
#include<iostream>
#include<unordered_map>
using namespace std;
const int N=110,mod=1e9+7;
typedef long long LL;
int main()
{
unordered_map<int,int> primes;
int n;
cin>>n;
LL res=1;
while(n--)
{
int x;
cin>>x;
for(int i=2;i<=x/i;i++)
while(x%i==0)
{
primes[i]++;
x/=i;
}
if(x>1)
primes[x]++;
}
for(auto p:primes)
res=res*(p.second+1)%mod;
cout<<res<<endl;
return 0;
}
(约数之和)
#include<iostream>
#include<unordered_map>
using namespace std;
const int N=110,mod=1e9+7;
typedef long long LL;
int main()
{
unordered_map<int,int> primes;
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
for(int i=2;i<=x/i;i++)
while(x%i==0)
{
primes[i]++;
x/=i;
}
if(x>1) primes[x]++;
}
LL res=1;
for(auto p:primes)
{
LL a=p.first,b=p.second;
LL t=1;
while(b--)
t=(t*a+1)%mod;
res=res*t%mod;
}
cout<<res<<endl;
return 0;
}
(最大公约数)
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x,y;
cin>>x>>y;
cout<<gcd(x,y)<<endl;
}
return 0;
}
(欧拉函数)
#include<iostream>
using namespace std;
int phi(int x)
{
int res=x;
for(int i=2;i<=x/i;i++)
if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0) x/=i;
}
if(x>1) res=res/x*(x-1);
return res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
cout<<phi(x)<<endl;
}
return 0;
}
(筛法求欧拉函数)
#include<iostream>
using namespace std;
const int N=1000010;
typedef long long LL;
int primes[N],cnt;
bool st[N];
int euler[N];
void get_eulers(int n)
{
euler[1]=1;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
euler[i]=i-1;
}
for(int j=0;primes[j]<=n/i;j++)
{
int t=primes[j]*i;
st[t]=true;
if(i%primes[j]==0)
{
euler[t]=euler[i]*primes[j];
break;
}
euler[t]=euler[i]*(primes[j]-1);
}
}
}
int main()
{
int n;
cin>>n;
get_eulers(n);
LL res=0;
for(int i=1;i<=n;i++) res+=euler[i];
cout<<res<<endl;
return 0;
}
(快速幂)
#include<iostream>
using namespace std;
typedef long long LL;
LL qmi(int a,int b,int p)
{
LL res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*(LL)a%p;
b>>=1;
}
return res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,b,p;
cin>>a>>b>>p;
cout<<qmi(a,b,p)<<endl;
}
return 0;
}
(快速幂求逆元)
#include<iostream>
using namespace std;
typedef long long LL;
LL qmi(int a,int b,int p)
{
LL res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*(LL)a%p;
b>>=1;
}
return res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,p;
cin>>a>>p;
if(a%p==0) cout<<"impossible"<<endl;
else cout<<qmi(a,p-2,p)<<endl;
}
return 0;
}
(拓展欧几里得算法)
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
else
{
int t=exgcd(b,a%b,y,x);
y-=a/b*x;
return t;
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
int x,y;
int temp=exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
return 0;
}
(线性同余方程)
#include<iostream>
using namespace std;
typedef long long LL;
LL exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
else
{
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,b,m;
cin>>a>>b>>m;
int x,y;
int d=exgcd(a,m,x,y);
if(b%d) puts("impossible");
else cout<<(LL)b/d*x%m<<endl;
}
return 0;
}
(表达整数的奇怪方式)
#include<iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
int n;
cin>>n;
LL a1,m1,x=0;
cin>>m1>>a1;
for(int i=0;i<n-1;i++)
{
LL a2,m2;
cin>>m2>>a2;
LL k1,k2;
int d=exgcd(m1,m2,k1,k2);
if((a2-a1)%d)
{
x=-1;
break;
}
k1*=(a2-a1)/d;
k1=(k1%(m2/d)+(m2/d))%(m2/d);
x=k1*m1+a1;
LL m=abs(m1/d*m2);
a1=k1*m1+a1;
m1=m;
}
if(x!=-1)
x=(a1%m1+m1)%m1;
cout<<x<<endl;
return 0;
}
(高斯消元解线性方程组)
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=110;
const double eps=1e-6;
double a[N][N];
int n;
int gauss()
{
int r,c;
for(r=0,c=0;c<n;c++)
{
int t=r;
for(int i=r;i<n;i++)
if(fabs(a[i][c])>fabs(a[t][c]))
t=i;
if(fabs(a[t][c])<eps) continue;
for(int i=c;i<n+1;i++) swap(a[t][i],a[r][i]);
for(int i=n;i>=c;i--) a[r][i]/=a[r][c];
for(int i=r+1;i<n;i++)
if(fabs(a[i][c])>eps)
for(int j=n;j>=c;j--)
a[i][j]-=a[r][j]*a[i][c];
r++;
}
if(r<n)
{
for(int i=r;i<n;i++)
if(fabs(a[r][n])>eps)
return 2;
else return 1;
}
for(int i=n-1;i>=0;i--)
for(int j=i+1;j<n;j++)
a[i][n]-=a[j][n]*a[i][j];
return 0;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n+1;j++)
cin>>a[i][j];
int t=gauss();
if(t==0)
{
for(int i=0;i<n;i++) printf("%.2lf\n",a[i][n]);
}
else if(t==1) puts("Infinite group solutions");
else puts("No solution");
return 0;
}