日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內(nèi)最全I(xiàn)T社區(qū)平臺 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > php開源 > php教程 > 51NOD 1434 區(qū)間LCM(素數(shù)篩)

51NOD 1434 區(qū)間LCM(素數(shù)篩)

來源:程序員人生   發(fā)布時間:2016-06-29 09:46:49 閱讀次數(shù):3609次

傳送門

1434 區(qū)間LCM
題目來源: TopCoder
基準(zhǔn)時間限制:1 秒 空間限制:131072 KB 分值: 40 難度:4級算法題 收藏 關(guān)注
1個整數(shù)序列S的LCM(最小公倍數(shù))是指最小的正整數(shù)X使得它是序列S中所有元素的倍數(shù),那末LCM(S)=X。
例如,LCM(2)=2,LCM(4,6)=12,LCM(1,2,3,4,5)=60。
現(xiàn)在給定1個整數(shù)N(1<=N<=1000000),需要找到1個整數(shù)M,滿足M>N,同時LCM(1,2,3,4,…,N⑴,N) 整除 LCM(N+1,N+2,….,M⑴,M),即LCM(N+1,N+2,….,M⑴,M)是LCM(1,2,3,4,…,N⑴,N) 的倍數(shù).求最小的M值。
Input
多組測試數(shù)據(jù),第1行1個整數(shù)T,表示測試數(shù)據(jù)數(shù)量,1<=T<=5
每組測試數(shù)據(jù)有相同的結(jié)構(gòu)構(gòu)成:
每組數(shù)據(jù)1行1個整數(shù)N,1<=N<=1000000。
Output
每組數(shù)據(jù)1行輸出,即M的最小值。
Input示例
3
1
2
3
Output示例
2
4
6
解題思路:

假定有質(zhì)數(shù)K,可以求出t,使得K的t次方恰好小于等于m(K^t<=m)那末lcm(1,2,…,m)分解質(zhì)因數(shù)中1定而且最多有t個質(zhì)數(shù)K連乘,其實我們可以就是求的質(zhì)數(shù)的最高次冪,這樣就能夠很快地吧lcm(1,2,…,m)分解質(zhì)因數(shù)那末怎樣把 lcm(n+1,n+2,…,m)分解質(zhì)因數(shù)呢依然假定質(zhì)數(shù)K,可以求出最大的t,和1個常數(shù)c(1<=c < K),使得 n+1<=c*K^t<=m
那末lcm(n+1,n+2,…,m)分解質(zhì)因數(shù)中1定而且最多有t個質(zhì)數(shù)K連乘。比如說質(zhì)數(shù)3,n=16,m=22,可以求的c=2,t=2,即17<=2*3^2=18<=22,這樣lcm(17,18,19,20,21,22)中最多有2個質(zhì)數(shù)3連乘既然知道怎樣求lcm(n+1,n+2,..,m)和lcm(1,2,..,m)了來探討1下怎樣求最小的m吧我們想讓這兩個lcm分解質(zhì)因數(shù)后完全1樣,也就是說連乘的質(zhì)數(shù)個數(shù)也完全相等。也就是說,對每一個質(zhì)數(shù)K都可以滿足,存在c和最大的t 使得n+1<=c*K^t<=m對大于n小于m的質(zhì)數(shù),我們假定是P,那末1定n+1<=P<=m,1定可以滿足條件所以我們就只看小于等于n的質(zhì)數(shù)就能夠了由于要使每一個小于N的質(zhì)數(shù)K,都存在c和最大的t 使得n+1<=c*K^t<=m,我們枚舉每個質(zhì)數(shù),并求得c和t,使得恰好c*K^t>=n,
答案就取最大的c*K^t,即 max( c*K^t )這樣lcm(1,2,…,m)和lcm(n+1,n+2,…,m)的分解質(zhì)因數(shù)后均最少有t個質(zhì)數(shù)K。如果終究m有 k^(t+1)<=m,那末這個K^(t+1)>n1定成立,故仍滿足條件
代碼:

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; typedef long long LL; const int MAXN = 1e6+5; LL p[MAXN]; bool prime[MAXN]; int k; void isprime() { k = 0; memset(prime, 0, sizeof(prime)); prime[0] = prime[1] = 1; for(LL i=2; i<MAXN; i++) { if(!prime[i]) { p[k++] = i; for(LL j=i*i; j<MAXN; j+=i) prime[j] = 1; } } } int main() { isprime(); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); int ans = 2; for(int i=2; i<=n; i++) { if(!prime[i])///素數(shù) { int sum = i; while(sum <= n/i) sum *= i; ans = max(ans, (n/sum+1)*sum); } } cout<<ans<<endl; } return 0; }

生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進(jìn)行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 久久久久久久av | 香蕉久操 | 国产在线播放不卡 | 久久久久国产精品一区 | 一区二区中文字幕 | 欧美日韩视频免费观看 | 黄a免费视频 | 日本视频久久 | 国产在线观看一区二区三区 | 久久久久99 | 国产精品二区三区 | 日韩美女视频 | 91精品国产乱码久久久久久久久 | 日韩国产精品一区二区 | 亚洲国产日韩欧美 | 中文字幕日韩电影 | 欧美一级特黄aa大片 | 国产精品三级视频 | 国产精品精品视频 | 天堂在线中文 | 国产一区二区中文字幕 | 亚洲第一免费播放区 | 人人九九精品 | 亚洲午夜久久久久久久久久久 | 日韩欧美h | 黄色网址在线播放 | 欧美日韩一二三 | 日本视频黄色 | 色播av| 久久视频一区 | 日韩欧美亚洲综合 | 天天综合网日日夜夜 | 日韩av首页| 亚洲一区二区三区在线免费观看 | av片在线观看免费 | 亚洲欧洲av在线 | 国产午夜精品一区二区 | 嫩草影业地址 | 成人欧美一区二区三区视频xxx | 女国产精品视频一区二区三区 | 免费成人高清 |