NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組初賽
 npsc2015國中組初賽 B.胖胖數

作者 主題: npsc2015國中組初賽 B.胖胖數  (閱讀 869 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
npsc2015國中組初賽 B.胖胖數
« 於: 十二月 10, 2015, 11:08:09 pm »

這一題的時限?   R-L最大差距是多少?   有測資嗎?
如果R-L<10^4而且時限10秒,我的以下想法也許有點希望
又如果 R-L 真的不會太大,而時間差一點,還可以將L~R的迴圈加快6n+1,6n+5
拋磚 希望能 引玉
代碼: [選擇]
/* npsc2015-j1b 胖胖數
這一題的時限? R-L最大差距是多少?有測資嗎?
如果R-L<10^4而且時限10秒,我的以下想法也許有點希望

我有三個函數
void genp(MaxN) 建一質數表,但MaxN不可能10^18,選個數字吧(就1e6)
    我用篩法建bool c[MaxN],並以vector<int> p存 2~MaxN之間的質數

bool isp(long long int k) 傳回是否為質數{簡稱p}

bool ispp( long long int k) 傳回是否胖胖數{簡稱pp}

    1算pp,我將k改為字串 s{假設有10位數abcdefghij} 分段算出sum=a, sum*10+b ,sum*10+c...
    分別判斷a,ab,abc,abcd...,abcdefghij是否為質數只要有一個非則傳回 false
 例 2339933917  {2:p, 23:p, 233:p, 2339:p, 23399:p, 233993:p,
    2339933:p, 23399339:p, 233993391:非p 則傳回 false}
 又例 293997390 {2:p, 29:p, 293:p, 2939:p, 29399:p, 293997:非p 則傳回 false }
*/
#include <iostream>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
const int MaxN = int(1e6); //50000; //int(1e7);
vector <int> p;
bool c[MaxN];
void genp(int maxn)
{
   int i,j;
   for(i=0;i<maxn;i+=2) c[i]=false , c[i+1]=true;
   c[1]=true;  c[2]=true;   p.push_back(2);
   for(i=3; i<maxn; i+=2)
   {
if( !c[i] ) continue;
p.push_back(i);
    for(j=i+i; j<maxn; j+=i)
      c[j]=false;
   }
   cout << p.size() << ":" << p[p.size()-1] << endl;
}
bool isp(long long int k)
{
   if(k<MaxN) return c[k];
   int q = int(sqrt(k));
int i,j;
for(i=0; i<p.size() && p[i]<=q; ++i)
   if(k%p[i]==0) return false;
cout << "[" << q <<":"<<p[i]<<"]"<<i <<endl;
   if(q<p[i]) return true;
for(i=p[p.size()-1]+2; i<=q; i+=2)
if(k%i==0) return false;
return true;
}
bool ispp(long long int kk)
{
stringstream ss;
string s;
ss << kk;  ss>>s;
  int i;
  long long int k=int(s[0]-'0');
  if( !isp(k) ) return false;
  for(i=1; i<s.size(); ++i)
  {
//if(s[i]=='0' || s[i]=='2' || s[i]=='4' || s[i]=='5' || s[i]=='6' || s[i]=='8') return false;
k=k*10+int(s[i]-'0');
if( !isp(k) ) return false;
  }
  return true;
}
int main()
{
   int i,j;
   genp(MaxN);
   int T;
   long long int L,R,k;
   cin >> T;
   while(T--)
   {
scanf("%lld %lld", &L, &R);
cout << L <<"," <<R << endl;
     int cnt=0;
     if(L<=2) { cnt=3-L; L=3;  cout <<"1 or 2 cnt:" << cnt <<" ]";}
     if(L%2==0) ++L;
   for(k=L; k<=R; k+=2)
   {
if( ispp(k) ) { printf("%lld ", k); ++cnt;}
  //cout <<fixed<<setprecision(10) << log10(k)<<" "<< k <<":" << isp(k) << endl;
   }
   printf("共 %d\n",cnt);
}
  return 0;
}
/*  ---輸入範例
20
1 11
10 100
100 900
1000 3000
37210 98765
3700 5700
1379 3791
13976 23977
1131111 1171111
1151110 1157110
7133271 7339271
31415926535 31415926535
1319399173131 1319399273131
2345789654328763 2345789654338763
77777771 77797771
979793910 979893910
31415926535 31415926535
31415926535 31415926535
323333 399999
23333 29999
---------------輸出範例
6
13
24
17
8
4
19
17
0
0
0
0
0
0
0
0
0
0
2
5

*/

« 上次編輯: 十二月 10, 2015, 11:16:50 pm 由 rscpp »
記錄

yuscvscv

  • 初級會員
  • **
  • 文章數: 30
    • 檢視個人資料
Re: npsc2015國中組初賽 B.胖胖數
« 回覆 #1 於: 十二月 15, 2015, 05:32:10 pm »

L, R差值沒有限制噢。目前應該抓的到原始題目吧?
時限的話,印象中只有1秒。

只能說你的作法不是官方期望作法,實際在場上的話會 TLE。
等測資出你可以玩玩XD
« 上次編輯: 十二月 15, 2015, 05:35:24 pm 由 yuscvscv »
記錄

vincent

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
Re: npsc2015國中組初賽 B.胖胖數
« 回覆 #2 於: 三月 15, 2016, 06:16:15 pm »

我有測試過,是在一秒內,請參考。

#include <stdio.h>

int main(void)
{
    int T;
    scanf("%d", &T);
    int answers[T];
   
    for (int i = 0 ; i < T ; i++)
    {
        long long L, R;
        scanf("%lld %lld", &L, &R);
        int a = 0;
       
        for (long long j = L ; j <= R ; j++)
        {               
            long long S = j;
            int x = 1;
            int array[19];
            array[0] = S;
            while(S >= 10)
            {
                S /= 10;                               
                array[x] = S;
                x++;
            }
            int temp[19];
            for (int k = 0, l = x - 1 ; l >= 0 ; k++, l--)
            {
                temp[k] = array[l];
            }
            for (int k = 0 ; k < x ; k++)
            {
                array[k] = temp[k];
            }
           
            for (int k = 0 ; k < x ; k++)
            {   
                int b = 0;
                if(array[k] > 3)
                {           
                    for (int l = 2 ; l < (int)(array[k] / 2 + 1) ; l++)
                    {   
                       
                        if(array[k] % l == 0)
                        {
                            b = 1;
                            break;
                        }
                        else if(k == x - 1 && l == (int)(array[k] / 2))
                        {   
                            a++;
                        }
                    }
                    if(b == 1)
                    {
                        break;
                    }
                }
                else if(k == x - 1 && array[k] <= 3)
                {
                    a++;
                }
            }
           
            answers = a;
        }
    }
   
    for (int i = 0 ; i < T ; i++)
    {
        printf("%d\n", answers);
    }
}
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組初賽
 npsc2015國中組初賽 B.胖胖數