题目：求一个最小的整数，能被1~n中的所有数整除。n的范围为 1 <= n <= 100000，答案对1e9+7取模。   思路：一上来有些人可能认为可以先求最小公倍数然后再取模，这样显然是不可以的，因为求最小公倍数中有除法，除法是不能直接取模的，就算用了逆元，也是不对的。 我们可以把每一个数进行质因数分解，之后求最小公倍数，最后用快速幂求出答案并取模就正确了。 举个例子： a = 16, b = 20，求a,b的最小公倍数 a有4个质因数2 b有2个质因数2，和1个质因数5 所以a,b的最小公倍数等于    2^max(4,2) * 5^max(0,1) = 80    #include #include #include #include #include #define LL long long using namespace std; const int maxn = 1e5 + 10; const int mod = 1e9 + 7; int f[maxn],p[maxn],cnt = 0; int b[maxn]; void prime() { LL i,j; f[1] = 1; for(i=2;i b[p[i]]) b[p[i]] = t; i++; } if(x > 1) b[x] = max(b[x],1); } LL qpow(LL x,int k) { LL ans = 1; while(k) { if(k&1) ans = ans*x%mod; x = x*x%mod; k /= 2; } return ans; } LL gcd(LL a,LL b) { if(b == 0) return a; else return gcd(b,a%b); } LL com(LL a,LL b) { return a/gcd(a,b)*b; } int main(void) { int n,i,j; prime(); scanf("%d",&n); memset(b,0,sizeof(f)); for(i=1;i<=n;i++) { fun(i); } LL ans = 1; for(i=2;i<=n;i++) { ans = ans*qpow(i,b[i])%mod; } cout << ans << endl; return 0; }