NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2014國中組決賽
 D 寧寧發糖果

作者 主題: D 寧寧發糖果  (閱讀 865 次)

skipper

  • 初級會員
  • **
  • 文章數: 28
    • 檢視個人資料
D 寧寧發糖果
« 於: 十二月 06, 2014, 03:08:40 pm »

/*
先用快篩法建立質數表再做!
http://www.csie.ntnu.edu.tw/~u91029/Prime.html
*/
代碼: [選擇]
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int S[77777];
const int MAX = 1000001;
bool prime[MAX];

void eratosthenes()
{
    for (int i=0; i<MAX; i++)  // 初始化
        prime[i] = true;
 
    prime[0] = false;   // 0 和 1 不是質數
    prime[1] = false;
 
    // 找下一個未被刪掉的數字
for (int i=2; i<MAX; i++){
if (prime[i]){
            // 刪掉質數i的倍數,從兩倍開始。保留原本質數。
            for (int j=i+i; j<MAX; j+=i)
                prime[j] = false;
}
}
}
int main(){
eratosthenes();
int T,n;
cin >>T;
while(T--){
cin >> n;
for (int i=0;i<n;i++){
cin >> S[i];
}
int largest = *max_element(S,S+n);
bool FOUND=false;
for (int j=2;j<=largest&&!FOUND;j++){
if(prime[j]){
int count=0;
for (int i=0;i<n&&!FOUND;i++){
if (S[i]%j==0) count++;
if (count==2) FOUND =true;
}
}
}
if (FOUND) cout <<"Yes"<<endl;
else cout << "No"<<endl;
}
return 0;
}
« 上次編輯: 十二月 06, 2014, 09:42:49 pm 由 sagit »
記錄

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
Re: D 寧寧發糖果
« 回覆 #1 於: 一月 24, 2015, 06:17:57 pm »

樓上的程式應會逾時吧,改寫如下
2~10^6 建表,出現次數,>=2 yes
再每個質數 跑一次,其倍數是否在 「讀入的數列」a[]中出現過 2次以上?
=======
本程式在 pc 上跑約 4.5 秒 ? cin+cout應會逾時
=======
代碼: [選擇]
/*
NPSC 2014 國中組決 D. 寧寧發糖果
2~10^6 建表,出現次數,>=2 yes
再每個質數 跑一次,其倍數是否在 「讀入的數列」a[]中出現過 2次以上?
=======
本程式在 pc 上跑約 4.5 秒 ? cin+cout應會逾時
=======
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#define MaxN 1000000
using namespace std;
bool m[MaxN];
long long p[78500]; // 1000000 內的質數 78498個
int ps;
void genp() //建 <=1000000的質數表
{
int i,j,k,q=int(sqrt(MaxN));
p[0]=2;
for(i=3; i<q; i+=2) // 只設定奇數
{
if(!m[i]) for(k=2*i, j=i*i; j<MaxN; j+=k ) m[j]=true;
}
for(ps=1, i=3; i<MaxN; i+=2 )
if(!m[i]) p[ps++] = i;
}
int d[MaxN+1];
int main( )
{
   genp();
int t,n,i,j,k;
scanf("%d",&t); // cin >>t;
while( t-- )
{
scanf("%d",&n); //cin >> n;
int a[n] , x=0;

for(i=0; i<n ; ++i)
{
scanf("%d",&a[i]); //cin >> a[i];
if(a[i]>x) x=a[i];
}
for(i=0;i<=x;++i) d[i]=0;
bool yes=false;
for(i=0; i<n ; ++i)
{
if( a[i]==1 ) continue;
if ( d[a[i]] >=1 ) { yes=true; break; }
else ++ d[a[i]];
}
// 判斷 所有 < x 的質數的 倍數 出現 在讀入數列 二個以上
for(i=0; i<ps && !yes; ++i) 
{
if( (k=p[i]) >= x ) break;
int cnt=0;
for( j=k; j<=x ;j+=k ) 
{
if( d[j]>=1 ) ++cnt;
}
   if(cnt>=2) { //
yes=true; break; };
}
if( yes ) printf("Yes\n");  //cout <<"Yes" << endl;
else printf("No\n");  //cout <<"No" << endl;
}   
   return 0;
}
/*
4
3 2 3 4
3 3 4 5
4 3 3 4 5
2 15 21
-------------
Yes
No
Yes
Yes

*/

記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2014國中組決賽
 D 寧寧發糖果