NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2014高中組初賽
 NPSC-2014-高中組初賽 D.小小郭的密碼( Not OK )

作者 主題: NPSC-2014-高中組初賽 D.小小郭的密碼( Not OK )  (閱讀 3033 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC-2014-高中組初賽 D.小小郭的密碼( Not OK )
« 於: 十一月 23, 2014, 10:05:08 pm »

這是來亂的,大家抱歉了!「數大就是{沒}
因題目沒看清,這個邏輯不通。

我的想法是先建表,然後再查對每組查詢的左值lv及右值rv定出其在表中的位置,即可得出數量

雙迴圈 i=1~10000, j=i+1~ i+49 建立連續數的乘積表{<=1e18 才存} set <LL > s
  將s轉至表中vector<LL > v 數字由小至大排序且不重複,
對每組查詢 lv , rv 找出 v[a]>=lv 且最接近的索引 a 、 v[ b] <= rv 且最接近的索引 b

先拋磚引玉,請高手指正,大家一起來補完。
代碼: [選擇]
/*
npsc 2014-高中組初賽 題目 D 小小郭的密碼

*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#define LL unsigned long long int
using namespace std;
set < LL > s;
set < LL >::iterator is;
vector < LL > v;

int bsrch(LL key , int u)  //二分搜找 v[m]<=key的 m
{
int l=0 , r=u  ;
int m = (l+r)/2 ;
while( v[m] != key && l<=r )
{
  if(v[m]>key) r = m-1;
  else l=m+1;
  m = (l+r)/2;
}
return m;
}

int main()
{

  int i,j,k,n,r,cnt=0;
  // 建表
    s.insert(0);
  for(i=1;i<=10000;++i)
  {
  LL  p=i;
  k=i+50; // 10^18 < 2^60 < 49!
    for(j=i+1; j<k && p < 10e18 ; ++j)
    {
if( (p>10e17 && j >10) || (p>10e16 && j>100) || (p>10e15 && j>1000) ) break;
p *= j;
if( p<=10e18) s.insert(p);
}
}
// 將 set 依序存入 vector
for(is=s.begin(); is!=s.end(); ++is) v.push_back(*is);

int u=v.size()-1;
// cout <<v.size() << "個," << v[0]<< "," << v[1]<< "," << v[u] << endl;
// for(i=0;i<=100;++i) { cout <<v[i]<<" "; if((i+1)%5==0) cout << endl; }
// 讀 lv rv 後,以二分搜定左右索引值

LL lv,rv;
int t , a , b;
cin >> t;
while(t--)
{
cin >>lv >> rv;
a = bsrch( lv , u );
if(v[a]!=lv) ++a;
b = bsrch( rv , u );
// cout << lv << ":" << v[a] << " ~ ";
// cout << v[b] << ":" << rv << endl;
if(b<a) cout << 0 << endl;
else cout << b-a+1 << endl;
}
  return 0;
}
/*
8
1 10
5 30
6 131
7 10
12 12
2 720
3 6333
10000 10000000000
--------
2
5
12
0
1
33
99
12521

*/
« 上次編輯: 十一月 26, 2014, 08:07:54 am 由 rscpp »
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: NPSC-2014-高中組初賽 D.小小郭的密碼
« 回覆 #1 於: 十一月 25, 2014, 04:17:09 pm »

感覺這樣的寫法並沒有把所有 x*(x+1) 的數都放進去,因為你的 i 只做到 10000,
所以如果是 10001*10002 這個數就不會出現在結果裡。
(還是我誤解題意了)
記錄

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
Re: NPSC-2014-高中組初賽 D.小小郭的密碼
« 回覆 #2 於: 十一月 26, 2014, 12:07:16 am »

謝謝sagit老師,我看錯了,把 t 看成是x的範圍,
怎麼改呢?
兩數相乘的 10^9以內的各跑1次要多久?
三數相乘的 10^6 ,再試試吧!
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: NPSC-2014-高中組初賽 D.小小郭的密碼( Not OK )
« 回覆 #3 於: 十一月 26, 2014, 08:30:20 am »

光是兩個數相乘所花的時候,
可能就超過3秒了,
如果真的要建表,
可能就跟2008年決賽F.數列那題類似,
先寫一個程式建表,
跑出所有的數字之後,
讓它變成陣列的起始值,
之後就可以用你說的二分搜來解。
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: NPSC-2014-高中組初賽 D.小小郭的密碼( Not OK )
« 回覆 #4 於: 十一月 26, 2014, 08:35:51 am »

如果不建表的話,
我目前想到的是先以兩個數相乘的部分,
以二分搜找出小於 l 的最大 x1 的值,
和小於等於 r 的最大 x2 的值,
兩者相減就是 l~r 之間有幾個可以用 x*(x+1) 表示的數,
再來找三個數相乘、四個數相乘,
一直找上去。
一次二分搜最多 20 次可以找到,
最多做到20個數字相乘,
(註:20!>1018)
所花時間 (20+20)*20*20,
應該有機會可以過。
« 上次編輯: 十一月 26, 2014, 08:44:45 am 由 sagit »
記錄

a00012025

  • 新手
  • *
  • 文章數: 2
    • 檢視個人資料
Re: NPSC-2014-高中組初賽 D.小小郭的密碼( Not OK )
« 回覆 #5 於: 十一月 26, 2014, 06:49:12 pm »

這是我比賽後寫的,隨機生了一些測資根AC這題的程式碼比對輸出都沒問題。
作法是建連續4個數以上的數相乘的所有數,然後連續兩個和三個的用二分搜,但其中會有重複算到的,共有四種:(以下簡記「可以被表為連續k個數相乘的數」為k乘數)
(1)一個數同時是m,n乘數(m,n>=4 , m!=n)
(2)一個數同時是3,m乘數(m>=4)
(3)一個數同時是2,m乘數(m>=4)
(4)一個數同時是2,3乘數(m>=4)
然後另外寫個程式算這些東西。(會發現沒有第三種數)

另一個作法是直接把>=4乘數存在同一個vector v 裡面,排序,然後用
v.resize( v.unique(v.begin(),v.end()) - v.begin() )
去掉重複的,並且在丟進vector前判斷他是不是2,3乘數,這樣最後要考慮的重複就只剩2且3乘數了,而滿足的只有6和210兩個數。
代碼: [選擇]
#include<bits/stdc++.h>
#define LL long long
using namespace std;
vector<LL> v[32] ;
int num[]={0,0,0,31621,3979,997,369,174,96,58,38,26,18,13,9,6,4,2,1,0} ;
LL mp[]={120,720,5040,175560,17297280,19958400,259459200,20274183401472000} ;
LL mp2[]={6,210,0} ;

void pre_cal()
{
    for(int i=3;i<=30;i++) v[i].clear() ;
    for(int i=3;i<=18;i++) for(int j=2;j<=num[i];j++)
    {
        LL M=j ;
        for(int k=1;k<=i;k++) M*=(j+k) ;
        v[i].push_back(M) ;
    }
}

LL cal_1(LL x)
{
    if(x<=2) return x==2 ? 1 : 0 ;
    LL l=1 , r=1e9 ;
    while(r-l>1)
    {
        LL mid=(l+r)/2 ;
        if(mid*(mid+1)>x) r=mid ;
        else l=mid ;
    }
    return l ;
}

LL cal_2(LL x)
{
    if(x<=6) return x==6 ? 1 : 0 ;
    LL l=1 , r=1e6 ;
    while(r-l>1)
    {
        LL mid=(l+r)/2 ;
        if(mid*(mid+1)*(mid+2)>x) r=mid ;
        else l=mid ;
    }
    return l ;
}

LL solve(LL x)
{
    LL ret=cal_1(x)+cal_2(x) ;
    for(int i=3;i<=18;i++)
    {
        int j ;
        for(j=0;j<v[i].size() && v[i][j]<=x;j++) ;
        ret += j ;
    }
    int minu1,minu2 ;
    for(minu1=0;minu1<8 && mp[minu1]<=x;minu1++) ;
    for(minu2=0;mp2[minu2]!=0 && mp2[minu2]<=x;minu2++) ;
    return ret-minu1-minu2 ;
}

main()
{
        //freopen("input.txt","r",stdin) ;
        //freopen("output1.txt","w",stdout) ;
    pre_cal() ;
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        LL l,r ; scanf("%I64d%I64d",&l,&r) ;
        printf("%I64d\n",solve(r)-solve(l-1)) ;
    }
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2014高中組初賽
 NPSC-2014-高中組初賽 D.小小郭的密碼( Not OK )