特定の範囲にいくつのPR番号が存在しますか?

0
sdrtg ghytui 2019-03-26 07:03.

宿題の問題ではありません。私はこの問題に興味があります。そして、私のアプローチは単純なブルートフォースです:-)

私のブルートフォースC++コード:

int main()
{
    ll l,r;
    cin>>l>>r;
    
    ll f=0;
    ll i=l;
    
    while(i<=r)
    {
        ll j=0;
        string s;
        ll c=0;
        s=to_string(i);

        // cout<<s<<" ";

        ll x=s.length();

        if(x==1)
        {
            c=0;
        }
        else 
        {
            j=0;
            //whil
            while(j<=x-2)
            {
                string b,g;

                b="1";
                g="1";
                
                b=s[j];
                g=s[j+1];
                
                ll k1,k2;
                
                k1=stoi(b);
                k2=stoi(g);

                if(__gcd(k1,k2)==1)
                {
                    c=1;
                    break;
                }
                
                j++;
            }
        }
        
        ll d=0;
        j=0;
        while(j<=x-1)
        {
            if( s[j]=='2' || s[j]=='3' || s[j]=='5' || s[j]=='7')
            {
                string b;
                b="1";
                b=s[j];
                ll k1=stoi(b);
                if(i%k1==0)
                {
                    //d=0;
                }
                else
                {
                    d=1;
                    break;
                }
            }
            j++;
        }
        if(c==1 || d==1)
        {
            // cout<<"NO";
        }
        else
        {
            f++;
            // cout<<"PR";
        }
        // cout<<"\n";
        
        i++;
    }
    
    cout<<f;
    
    return 0;
}

2つの整数「L」と「R」が与えられます。'L'から 'R'の範囲のすべてのPR番号のカウントを見つける必要があります。PR番号は、次の特性を満たす番号です。

  1. 隣接する数字のペアは互いに素ではありません。つまり、PR番号の隣接する数字は互いに素ではありません。

  2. PR番号は、PR番号の1桁として出現するすべての1桁の素数で割り切れます。

注:gcd(a、b)= 1の場合、2つの数値「a」と「b」は互いに素です。

また、gcd(0、a)= a;

例:
入力:[2,5]。
出力:「4」。

(注:「1」は非常に一般的ですが、素数ではありません)

(すべての整数: '2'、 '3'、 '4'、 '5')はPR番号の条件を満たす:-)

'L'、 'R'の制約1 <= L, R <= 10^18

これを解決するための最も効率的なアルゴリズムは何でしょうか?

3 answers

0
juvian 2019-03-26 08:28.

注:これにより、隣接する数字のペアが互いに素ではないパート1のみが解決されます。つまり、PR番号の隣接する数字は互いに素ではありません。

Pythonでの建設的なアプローチは次のとおりです。範囲内のすべての数値を調べて条件でフィルタリングする代わりに、条件を満たすすべての数値を作成します。有効な数字のシーケンスがある場合、それが引き続き有効であるためには、次の数字が何であるかを決定するために、右端の数字のみが重要であることに注意してください。

def ways(max_number, prev_digit, current_number):
    if current_number > max_number:
        return 0
    count = 1
    if prev_digit == 0:
        if current_number != 0:
            count += ways(max_number, 0, current_number * 10)
        for i in range(2, 10): 
            count += ways(max_number, i, current_number * 10 + i)
    if prev_digit == 2 or prev_digit == 4 or prev_digit == 8:
        for i in [0, 2, 4, 6, 8]:
            count += ways(max_number, i, current_number * 10 + i)
    if prev_digit == 3 or prev_digit == 9:
        for i in [0, 3, 6, 9]:
            count += ways(max_number, i, current_number * 10 + i)
    if prev_digit == 5 or prev_digit == 7:
        count += ways(max_number, 0, current_number * 10)
        count += ways(max_number, prev_digit, current_number * 10 + prev_digit)
    if prev_digit == 6:
        for i in [0, 2, 3, 4, 6, 8, 9]:
            count += ways(max_number, i, current_number * 10 + i)
    return count

max_numberまでのすべての有効な数値を繰り返しなしで生成しているため、この関数の複雑さはO(条件1を満たす0からmax_numberまでの数値の量)です。aからbの範囲を計算するには、を実行する必要がありますways(b) - ways(a - 1)

結果を満たす42935の数値しかないため、これらの数値を0から100万まで計算するのに1秒もかかりません。条件を満たす数が少ないので、素数の倍数であるかどうかを確認して、条件2も満たすことができます。複数の方法があるので、この部分は読者に任せます。

0
user202729 2019-03-27 04:57.

TL; DR:これはより一般的に「ビットマスクを使用した数字動的計画法」と呼ばれます

より競争力のあるプログラミングに馴染みのある用語では、Rの最初の桁によって形成され、他のプロパティが一致する数よりも少ない、数字(先行ゼロを含む)をdp[n_digit][mod_2357][is_less_than_r][digit_appeared][last_digit]持つ数を計算します。RとL-1で2回実行してから、差を取ります。必要な操作の数は約19(桁数)* 210(mod)* 2 * 2 4(1桁の素数の出現を確認するだけです)* 10 * 10であり、これは明らかに今日のコンピューターで管理可能です。n_digitn_digit


番号が有効かどうかを確認する方法を考えてください。

通常の方法ではありません。入力を左から右に1桁ずつ受け取る有限状態オートマトンを使用します。

簡単にするために、入力の桁数が固定されていると仮定します(L / Rとの比較が容易になるように。これは、数値の桁数が最大でRであるため可能です)。

各州が以下を追跡する必要があります。

  • どの桁が数字に現れたか(ビットマスクを使用してください。1桁の素数は4つあります)
  • は範囲[L..R]の数値です(これはプレフィックスによってtrue / falseであることが保証されます。そうでない場合、プレフィックスはL / Rのプレフィックスと一致します)
  • 各1桁の素数の接頭辞modの値は何ですか
  • 最新の数字(連続する数字のすべてのペアが互いに素であるかどうかを確認するため)

有限状態オートマトンが構築された後、残りは簡単です。動的計画法を使用して、開始状態から受け入れられた状態へのパスの数を数えるだけです。


備考:このメソッドは、有限状態オートマトンを使用して検証できる任意のタイプのオブジェクトの数をカウントするために使用できます(大まかに言えば、一定のメモリ使用量のプログラムを使用してプロパティが満たされているかどうかを確認し、オブジェクトピースを取得できます-いくつかの順序で)

0
גלעד ברקן 2019-04-06 05:41.

有効な数を構成するために、プレフィックスと一致するサフィックスの数を検索できるテーブルが必要です。プレフィックスが与えられた

right digit
prime combination
mod combination

接尾辞の長さ、検索可能な接尾辞の数が必要です。

left digit
length
prime combination
mod combination

Pythonでコーディングを開始し、スニペットを提供できるようにJavaScriptに切り替えました。コード内のコメントは、各ルックアップテーブルを説明しています。より高速な列挙を可能にするためにそれらのいくつかがあります。テーブルを使用して任意の上限を構築する方法を説明するためのプレフィックスサフィックス計算のサンプルがありますが、少なくとも一部、おそらくすべてのプレフィックスの構築と集計を集計中に行うことができます。

function gcd(a,b){
  if (!b)
    return a
  else
    return gcd(b, a % b)
}

// (Started writing in Python,
// then switched to JavaScript...
// 'xrange(4)' -> [0, 1, 2, 3]
// 'xrange(2, 4)' -> [2, 3]
function xrange(){
  let l = 0
  let r = arguments[1] || arguments[0]
  if (arguments.length > 1)
    l = arguments[0]
  return new Array(r - l).fill(0).map((_, i) => i + l)
}

// A lookup table and its reverse,
// mapping each of the 210 mod combinations,
// [n % 2, n % 3, n % 5, n % 7], to a key
// from 0 to 209.
// 'mod_combs[0]' -> [0, 0, 0, 0]
// 'mod_combs[209]' -> [1, 2, 4, 6]
// 'mod_keys[[0,0,0,0]]' -> 0
// 'mod_keys[[1,2,4,6]]' -> 209
let mod_combs = {}
let mod_keys = {}
let mod_key_count = 0
for (let m2 of xrange(2)){
  for (let m3 of xrange(3)){
    for (let m5 of xrange(5)){
      for (let m7 of xrange(7)){
        mod_keys[[m2, m3, m5, m7]] = mod_key_count
        mod_combs[mod_key_count] = [m2, m3, m5, m7]
        mod_key_count += 1
      }
    }
  }
}

// The main lookup table built using the
// dynamic program
// [mod_key 210][l_digit 10][suffix length 20][prime_comb 16]
let table = new Array(210)
for (let mk of xrange(210)){
  table[mk] = new Array(10)
  for (let l_digit of xrange(10)){
    table[mk][l_digit] = new Array(20)
    for (let sl of xrange(20)){
      table[mk][l_digit][sl] = new Array(16).fill(0)
    }
  }
}

// We build prime combinations from 0 (no primes) to
// 15 (all four primes), using a bitmask of up to four bits.
let prime_set = [0, 0, 1<<0, 1<<1, 0, 1<<2, 0, 1<<3, 0, 0]

// The possible digits that could
// follow a digit
function get_valid_digits(digit){
  if (digit == 0)
    return [0, 2, 3, 4, 5, 6, 7, 8, 9]
  else if ([2, 4, 8].includes(digit))
    return [0, 2, 4, 6, 8]
  else if ([3, 9].includes(digit))
    return [0, 3, 6, 9]
  else if (digit == 6)
    return [0, 2, 3, 4, 6, 8, 9]
  else if (digit == 5)
    return [0, 5]
  else if (digit == 7)
    return [0, 7]
}

// Build the table bottom-up

// Single digits
for (let i of xrange(10)){
  let mod_key = mod_keys[[i % 2, i % 3, i % 5, i % 7]]
  let length = 1
  let l_digit = i
  let prime_comb = prime_set[i]
  table[mod_key][l_digit][length][prime_comb] = 1
}

// Everything else
// For demonstration, we just table up to 6 digits
// since either JavaScript, this program, or both seem
// to be too slow for a full demo.
for (let length of xrange(2, 6)){
  // We're appending a new left digit
  for (let new_l_digit of xrange(0, 10)){
    // The digit 1 is never valid
    if (new_l_digit == 1)
      continue

    // The possible digits that could
    // be to the right of our new left digit      
    let ds = get_valid_digits(new_l_digit)

    // For each possible digit to the right
    // of our new left digit, iterate over all
    // the combinations of primes and remainder combinations.
    // The ones that are populated are valid paths, the
    // sum of which can be aggregated for each resulting
    // new combination of primes and remainders.
    for (let l_digit of ds){
      for (let p_comb of xrange(16)){
        for (let m_key of xrange(210)){
          new_prime_comb = prime_set[new_l_digit] | p_comb
          // suffix's remainder combination
          let [m2, m3, m5, m7] = mod_combs[m_key]
          // new remainder combination
          let m = Math.pow(10, length - 1) * new_l_digit
          let new_mod_key = mod_keys[[(m + m2) % 2, (m + m3) % 3, (m + m5) % 5, (m + m7) % 7]]

          // Aggregate any populated entries into the new
          // table entry
          table[new_mod_key][new_l_digit][length][new_prime_comb] += table[m_key][l_digit][length - 1][p_comb]
        }
      }
    }
  }
}


// If we need only a subset of the mods set to
// zero, we need to check all instances where
// this subset is zero. For example,
// for the prime combination, [2, 3], we need to
// check all mod combinations where the first two
// are zero since we don't care about the remainders
// for 5 and 7: [0,0,0,0], [0,0,0,1],... [0,0,4,6]
// Return all needed combinations given some
// predetermined, indexed remainders.
function prime_comb_to_mod_keys(remainders){
  let mod_map = [2, 3, 5, 7]
  let mods = []
  for (let i of xrange(4))
    mods.push(!remainders.hasOwnProperty(i) ? mod_map[i] - 1 : 0)
  
  function f(ms, i){
    if (i == ms.length){
      for (let idx in remainders)
        ms[idx] = remainders[idx]
      return [mod_keys[ms]]
    }    
    let result = []
    for (let m=ms[i] - 1; m>=0; m--){
      let _ms = ms.slice()
      _ms[i] = m
      result = result.concat(f(_ms, i + 1))
    }
    return result.concat(f(ms, i + 1))
  }
  return f(mods, 0)
}

function get_matching_mods(prefix, len_suffix, prime_comb){
  let ps = [2, 3, 5, 7]
  let actual_prefix = Math.pow(10, len_suffix) * prefix
  let remainders = {}
  for (let i in xrange(4)){
    if (prime_comb & (1 << i))
      remainders[i] = (ps[i] - (actual_prefix % ps[i])) % ps[i]
  }
  return prime_comb_to_mod_keys(remainders)
}

// A brute-force function to check the
// table is working. Returns a list of
// valid numbers of 'length' digits
// given a prefix.
function confirm(prefix, length){
  let result = [0, []]
  let ps = [0, 0, 2, 3, 0, 5, 0, 7, 0, 0]
  let p_len = String(prefix).length

  function check(suffix){
    let num = Math.pow(10, length - p_len) * prefix + suffix
    let temp = num
    prev = 0
    while (temp){
      let d = temp % 10
      if (d == 1 || gcd(prev, d) == 1 || (ps[d] && num % d))
        return [0, []]
      prev = d
      temp = ~~(temp / 10)
    }
    return [1, [num]]
  }

  for (suffix of xrange(Math.pow(10, length - p_len))){
    let [a, b] = check(suffix)
    result[0] += a
    result[1] = result[1].concat(b)
  }
  return result
}

function get_prime_comb(prefix){
  let prime_comb = 0
  while (prefix){
    let d = prefix % 10
    prime_comb |= prime_set[d]
    prefix = ~~(prefix / 10)
  }
  return prime_comb
}

// A function to test the table
// against the brute-force method.
// To match a prefix with the number
// of valid suffixes of a chosen length
// in the table, we want to aggregate all
// prime combinations for all valid digits,
// where the remainders for each combined
// prime combination (prefix with suffix)
// sum to zero (with the appropriate mod).
function test(prefix, length, show=false){
  let r_digit = prefix % 10
  let len_suffix = length - String(prefix).length
  let prefix_prime_comb = get_prime_comb(prefix)

  let ds = get_valid_digits(r_digit)
  let count = 0

  for (let l_digit of ds){
    for (let prime_comb of xrange(16)){
      for (let i of get_matching_mods(prefix, len_suffix, prefix_prime_comb | prime_comb)){
        let v = table[i][l_digit][len_suffix][prime_comb]
        count += v
      }
    }
  }

  let c = confirm(prefix, length)
  
  return `${ count }, ${ c[0] }${ show ? ': ' + c[1] : '' }` } // Arbitrary prefixes for (let length of [3, 4]){ for (let prefix of [2, 30]){ console.log(`prefix, length: ${ prefix }, ${ length }`) console.log(`tabled, brute-force: ${ test(prefix, length, true) }\n\n`)
  }
}

let length = 6
for (let l_digit=2; l_digit<10; l_digit++){
  console.log(`prefix, length: ${ l_digit }, ${ length }`)
  console.log(`tabled, brute-force: ${ test(l_digit, length) }\n\n`)
}

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

モンサントは世界で最も強力な遺伝子編集ツールにアクセスできるようになりました

モンサントは世界で最も強力な遺伝子編集ツールにアクセスできるようになりました

画像:AP通信の農業会社であるモンサントは、MITのブロード研究所とハーバード大学からCRISPR / Cas9遺伝子編集システムを使用するための非独占的なグローバルライセンス契約を取得しました。同社はこれを使用して新しい種子や植物を設計および栽培しますが​​、モンサントがこの革新的な新技術を悪用するのを防ぐために、その使用には重要な制限があります。

グーグルのAIが囲碁世界チャンピオンの李世ドルとの最初の試合に勝った

グーグルのAIが囲碁世界チャンピオンの李世ドルとの最初の試合に勝った

画像提供:Linh Nguyen一連の試合の最初の試合で、Google Deepmindの強力な人工知能AlphaGoが囲碁の世界チャンピオンであるリーセドルを打ち負かしました。セドルとDeepMindの試合(実際には5つのうちの最初の試合)がYouTubeで生放送されました。 3月9日。

アマゾンのタイルスポーツとタイルプロブラックフライデーのお得な情報には無料のエコードットが付属しています

アマゾンのタイルスポーツとタイルプロブラックフライデーのお得な情報には無料のエコードットが付属しています

タイルトラッカーは、鍵を見つけることができないためにいつも遅れている友人に素晴らしい贈り物をします(真剣に、彼らはとても時間厳守です、誰もがいつもそれを言っています、彼らは彼らの鍵を見つけることができませんでした!)、そしてAmazonのタイルブラックフライデーのお得な情報彼ら(またはあなた自身)のためにいくつかを購入するのは簡単です。ここでは3つの選択肢があります:私のお金のために、それはプロを取得する価値があります。

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

Tomorrow's Kitchen シリコンストレッチ蓋 12個パック | $14 | アマゾン | プロモーション コード 20OFFKINJALids は基本的にキッチンの靴下です。常に迷子になり、二度と閉じられない孤立したコンテナーが残ります。しかし、蓋が伸びて、残った容器、鍋、フライパン、さらには大きなスライスされた果物のすべてに適合するとしたらどうでしょうか? その非常に特殊な蓋を失うことを二度と心配する必要はありません。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

メリック・ガーランドはアメリカに失敗しましたか?

バイデン大統領の任期の半分以上です。メリック・ガーランドは何を待っていますか?

メリック・ガーランドはアメリカに失敗しましたか?

人々にチャンスを与えることは、人生で少し遅すぎると私は信じています。寛大に。

Language