辗转相除法
int gcd (int a,int b){
return b? gcd(b,a%b):a;
}
自适应辛普森公式 数值积分
在计算积分时,可以通过曲边梯形面积求和,然后求极限
或者可以通过直接通过原函数计算
但是对于复杂函数积分,可以通过二阶曲线拟合的方式进行计算
二阶函数拟合近似(b-a)(f(a)+f(b)+4f((a+b)/2)/6
可以通过递归的方式计算
const double eps=1e-12;
//被积函数
double f(double x){
return sin(x)/x;
}
double simpson(double a,double b){
double mid=(a+b)/2;
return (b-a)*(f(a)+f(b)+4*f(mid))/6;
}
//递归函数
double solve(double a,double b,double ans){
double mid=(a+b)/2;
double left=simpson(a,mid),right=simpson(mid,b);
//递归的边界条件
if(fabs(left+right-ans)<eps){
return left+right;
}
else return solve(a,mid,left)+solve(mid,b,right);
}
复合辛普森积分 将积分区间尽可能分的细,达到精度,不需要进行递归
const double eps = 1e-12 ;
double f(double x)
{
return sin(x)/x ;
}
double simpson(double l , double r)
{
double mid = (l+r) / 2 ;
return (r-l) * (f(l) + 4*f(mid) + f(r)) / 6 ;
}
int main()
{
double l ,r ;
cin >> l >> r ;
double h = (r-l)/350 ;
double res = 0 ;
double last = l ;
for(int i = 0 ; i <350 ; i ++ )
{
res += simpson(last , last + h) ;
last += h ;
}
printf("%lf\n" , res ) ;
return 0 ;
}
快速幂
int qmi(int a, int b, int p){
int res = 1;
while(b){
if(b & 1) res = (LL)res * a % p;
b >>= 1;
a = (LL)a * a % p;
}
return res % p;
}
倍数法求1~N的所有数的约数
vector<int> v[100001];
for(int i=1;i<=n;i++){
for(int j=1;j<=n/i;j++){
v[i*j].push_back(i);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<v[i].size();j++){
cout<<v[i][j]<<" ";
}
cout<<endl;
}
求一个整数的逆序数
int reverse(int n){
int res=0;
while(n){
res*=10;
res+=n%10;
n/=10;
}
return res;
}