倪文迪陪你学藍橋杯2021冬休み毎日一題:1.16日(2018省試合A組第4題)

2021年冬休み毎日1題、2017~2019年の省試合本題.本文の内容は倪文迪(華東理工大学コンピュータ学部ソフトウェア192クラス)と羅勇軍先生から提供された.次の毎日の問題は、新しいブログを出します.毎日ブルーブリッジカップのコラムを見てください.https://blog.csdn.net/weixin_43914593/category_10721247.html
各問題にはC++、Java、Pythonの3言語のコードが提供されている.Pythonは強力で威厳があり、符号化が簡潔であるため、後のブログは主にPythonコードで解釈され、もちろんC++とJavaのコードが添付されている.
文書ディレクトリ

1、題名説明

2、説明

3、Pythonコード

3.1暴力捜査

3.2硬算+並べ替え

3.3優先キュー+setデポジット

4、C++コード

4.1暴力捜査

4.2優先キュー+mpデウェイト

4.3 set+upper_bound

5、Javaコード

5.1暴力捜査

5.6優先キュー+setデポジット

2018省試合A組第4題、タイトルリンク:いくつ目のラッキー数http://oj.ecustacm.cn/problem.php?id=1362
1、テーマの説明
x星を旅行する観光客は、観光客番号として整数で送られます.x星の王は変な癖があって、彼は数字3,5と7しか好きではありません.王は、観光客の番号に因子:3,5,7だけが含まれていれば、賞品をもらうことができると規定しています.上位10のラッキーナンバーは:3 5 7 9 15 21 25 27 35 45で、11番目のラッキーナンバーは:49小明がラッキーナンバー5908470958505を受け取った.賞をもらうとき、これが何番目のラッキーな数字だと正確に言ってください.そうしないと、賞品がもらえません.明ちゃんの計算を手伝ってください.59084709587505はいくつかのラッキーな数字です.
2、説明
ゞ  填空,送分?ゞ  59084709587505という数はそれほど大きくなく,C++のunsigned long型で,最大値は2 64−1=18446744073709551615^{64}−1=18446744073709551615 264−1=18446744073709551615であった.
3、Pythonコード
3.1暴力捜査
このシリーズの数は3 iと表すことができる× 5 j × 7 k 3^i\times5^j\times7^k 3i×5j×7 k、範囲を超えないすべてのi、j、k i、j、k i、j、kの組み合わせを検索すればよい.  Pythonは大数の心配はありませんので、ループのついでに大きな範囲を取って終了条件にすればいいのですが、次のコードの3 50 3^{50}350は59084709587505を超えるに違いありません.

cnt = 0
for i in range(50):
    for j in range(50):
        for k in range(50):
            r1 = 3**i
            r2 = 5**j
            r3 = 7**k
            if r1*r2*r3 < 59084709587505:  #     <=
                cnt += 1
print(cnt )

3.2ハード計算+ソート
  Python符号化は極めて容易であるため、すべての3、5、7の倍数を無理に算出してから、59084709587505の位置を並べ替えて見つけても、符号化は容易である.

n = 59084709587505
a = [1]           # 3、5、7   
k = 0
while True: 
    for i in range(3, 8, 2):    #  3、5、7
        tmp = i*a[k]            #      
        if tmp not in a:        #  
            a.append(tmp)       #   
            a.sort()            #  
        if tmp > 2**64:         #          
            print(a.index(n))   #  
            exit(0)
    k += 1

3.3優先キュー+setデリバリー
  上の「3.2硬算+ソート」の考え方は、優先キューで実現できる.新しい数が生成されるたびに優先キューに入れる.キューからポップアップされるたびに最小であり、ソートを実現することに相当する.またキューに入れるときはsetで重み付けする.

import queue
 
q = queue.PriorityQueue()   #    ，    
s = set()                   #      
q.put(1)    
s.add(1)    
cnt = 0
while True:
    n = q.get()
    if n == 59084709587505:
        break
    cnt += 1
    for i in range(3, 8, 2):     #3、5、7
        t = n * i                #      
        if t not in s:           #  
            q.put(t)
            s.add(t) 
print(cnt)

4、C++コード
以下にC++のいくつかの実装を示し,説明するのがおっくうである.
4.1暴力捜査

#include
using namespace std;
int main(void){
     
    long long n = 59084709587505;
    int cnt = 0;
    for(int i=0;pow(3,i)<n;i++)    //     <=
        for(int j=0;pow(5,j)<n;j++)
            for(int k=0;pow(7,k)<n;k++)
                if(pow(3,i)*pow(5,j)*pow(7,k)<n)
                    cnt++;
    cout<<cnt;
    return 0;
}

4.2優先キュー+mpデポジット

//new oj User: 190101041
#include 
#define ll long long
using namespace std;
typedef priority_queue<ll,vector<ll>,greater<ll> > pq;
typedef map<ll,int> mp;
mp vis;
int sum[5]={
     3,5,7};
int main(){
     
   ll tem=59084709587505;
 
    pq qu;
    qu.push(1);
    int ans=0;
    while(1){
     
        ll cnt=qu.top();
        qu.pop();
        if(cnt==tem){
     
           cout<<ans<<endl;
           break;
        }
        ll temcnt;
        for(int i=0;i<3;i++){
     
            temcnt=cnt*sum[i];
            if(vis[temcnt]==0){
     
                qu.push(temcnt);
                vis[temcnt]=1;
            }
        }
        ans++;
    }
}

4.3 set+upper_bound

//new oj User: 311706000426
#include
using namespace std;
typedef long long LL;
set<LL> se; 
int main(){
     
    LL f = 1;
    LL a[3] = {
     3,5,7};
    while(1){
     
        for(int i=0;i<3;i++)
            if(f*a[i]<=59084709587505) 
            	se.insert(f*a[i]);
        f = *se.upper_bound(f);
        if(f>=59084709587505) 
        	break;
    }
    cout<<se.size();
 
    return 0;
}

5、Javaコード
5.1暴力捜査

public class Main{
     
    public static void main(String[] args) {
     
        int count=0;
        long n=59084709587505L;
        for(int i=0;Math.pow(3,i)<n;i++){
     
            for(int j=0;Math.pow(5,j)<n;j++){
     
                for(int k=0;Math.pow(7,k)<n;k++){
     
                    if(Math.pow(3,i)*Math.pow(5,j)*Math.pow(7,k)<n){
     
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

5.6優先キュー+setデリバリー

//new oj User: coder370
import java.util.*; 
public class Main {
     
    public static void main(String[] args) {
     
        Scanner sc = new Scanner(System.in) ;
        long n = 59084709587505L ; 
        int x=0,y=0,z=0 ; 
        long t=n ; 
        while(t%3==0) {
     t/=3;++x;}
        while(t%5==0) {
     t/=5;++y;}
        while(t%7==0) {
     t/=7;++z;}
        int mx=Math.max(x,y) ; 
        mx = Math.max(mx, z) ; 
        PriorityQueue<Long> q = new PriorityQueue<Long>() ; 
        Set<Long> st = new HashSet<Long>() ; 
        long[] num = {
     3,5,7} ; 
        for(int i=0 ; i<3 ;  ++i) {
     q.add(num[i]) ; st.add(num[i]);}
        int cnt=0 ; 
        while(q.isEmpty()==false) {
     
            long h = q.poll() ;
            ++cnt ; 
            if(h==n)    break ;
            for(int i=0 ; i<3 ; ++i) {
     
                t = h*num[i] ; 
                if(t>n)  continue ; 
                if(st.contains(t)==false) {
     
                    q.add(t) ;
                    st.add(t) ; 
                }
            }
        }
        System.out.println(cnt);
    }
}