【信奥数学基础】最小公倍数与不等式证明

【题】洛谷P6659 最小公倍数

给出z个整数M，求区间[a,b]，满足区间内所有数的最小公倍数为M。

先上AC代码

# include <bits/stdc++.h>
using namespace std;
long long M,d,dp[50];  
map<long long,int[2]> mp;
int z;
long long gcd(long long x,long long y){ return y? gcd(y,x%y) : x;}
void putmp(long long key, int l, int r){if(mp.find(key)==mp.end()) mp[key][0]=l, mp[key][1]=r;else if(mp[key][0]>l) mp[key][0]=l, mp[key][1]=r;else if(mp[key][0]==l && mp[key][1]>r) mp[key][1]=r;	
}
void chk2(long long x){ // 检查长度为2的区间[a,a+1], x==a(a+1) ?long long a=sqrt(x);if(a*(a+1)==x)putmp(x,a,a+1);
} 
void chk3(long long x){ // 检查长度为3的区间 long long a=pow(x,1.0/3.0),a2=pow(2*x,1.0/3.0);// 首数为偶数，则gcd为2if(a%2 && a*(a+1)*(a+2)==x) putmp(x,a,a+2);if(a2%2==0 && a2*(a2+1)*(a2+2)==2*x) putmp(x,a2,a2+2);
}
int main(){cin>>z;for(int a=1;a<1e6;a++){ dp[1]=1ll*a*(a+1);dp[2]=dp[1]*(a+2); if(a%2==0)dp[2]/=2; // 不能更新所有区间2/3，会MLE for(int j=3;j<45;j++){d=dp[j-1]/gcd(dp[j-1],a+j);if(d>=(1e18)/(a+j))break;dp[j]=d*(a+j);putmp(dp[j],a,a+j);}}while(z-->0){cin>>M;chk2(M),chk3(M);if(mp.find(M)!=mp.end()) cout<<mp[M][0]<<" "<<mp[M][1]<<endl;else cout<<"NIE"<<endl;	}return 0;
} 

这题数据规模较大(M<=1e18)，所以需要一些数学证明确定遍历的边界。

求证：

1. gcd(a,a+1)==1  && lcm(a,a+1)==a*(a+1)
2. gcd( lcm(a,a+1), a+2]) == (a%2)?1:2   
   && lcm([a,a+2]) == lcm( lcm(a,a+1), a+2) == a*(a+1)*(a+2) / ( (a%2)?1:2 )
3. 如果 M==a*(a+1)，必有 a=int(sqrt(M))
4. 如果 M==a*(a+1)*(a+2)，必有 a=int( M**(1/3))
5. 当 j>=3， 如果[a, a+j] 区间所有数的最小公倍数是M(<=1e18)，那么a<1e6

提示：前2题可用整除和最小公倍数的概念。后三题可用不等式的性质。