入力番号で割り切れる数が見つかった場合

Question

aとbの2つの数が与えられた場合、aまたはbで割り切れるn番目の数を見つけなければなりません。

入力： 最初の行は、テストケースの数を表す整数Tから成る

フォーマットは以下のように見えます。 セカンドラインは三つの整数、b及びN

出力含ま：各テストケースについて を、新しい行のn番目 番号を印刷します。

制約：

1≤t≤105

1≤a、b≤104

1≤N≤10

サンプル入力

サンプル出力

説明

2又は3で割り切れる数である：2,3,4,6,8 、9,10,12,14,15、10番目の数字は15

マイコード

test_case=input() 

if int(test_case)<=100000 and int(test_case)>=1: 
    for p in range(int(test_case)): 
     count=1 
     j=1 

     inp=list(map(int,input().strip('').split())) 
     if inp[0]<=10000 and inp[0]>=1 and inp[1]<=10000 and inp[1]>=1 and inp[1]<=1000000000 and inp[1]>=1: 
      while(True): 
      if count<=inp[2] : 
       k=j 
       if j%inp[0]==0 or j%inp[1] ==0: 
        count=count+1 
        j=j+1 

       else  : 
        j=j+1 
      else: 
       break 
      print(k)  
     else: 
      break 

問題文：単一のテストケース入力の場合 2000 3000 100000私が1秒未満で結果を得ることができる場合complete.Iに1秒以上は欲しい取っています。この問題に対する時間効率的なアプローチがありますか？ここでデータ構造とアルゴリズムを使用できるのでしょうか？

Answer 1

あなたが達成しようとしていることを正確に把握することは確実ではありません。しかし、私がそれを正しくするならば、答えは単にb *（N/2）ではないのですか？あなたは両方の数の倍数を列挙しているので、N番目の列は常にN/2番目の列の2番目の列になります。

最初の例では、3 * 10/2 = 15となります。コード例で 、3000 * 2分の100000 = 150'000'000

更新あろう： コード計算プロセスをスピードアップするためにセットのリストとを用いて所望の値を計算します。私はまだこのコードは、私のラップトップ上で0.14sで実行

a = 2000 
b = 3000 
c = 100000 

a_list = [a*x for x in range(1, c)] 
b_list = [b*x for x in range(1, c)] 

nums = set(a_list) 
nums.update(b_list) 

nums = sorted(nums) 

print(nums[c-1]) 

...誰もがそれにつまずくことを起こる場合は奇数インデックスの再発は何ができるかと思いまして。要求されたしきい値を大幅に下回っています。それにもかかわらず、この値はコードが実行されるマシンによって異なります。

Answer 2

2つの数字ごとにkのようになり、k=a*bとなります。 とbの倍数はkの下にだけ多くあります。このセットはそうのように作成することができます。

s = set(a*1, b*1, ... a*(b-1), b*(a-1), a*b) 

は、私たちが値a=2, b=3その後、s = (2,3,4,6)を取ると言います。可能な値はcです。

[1 - 4] => (2,3,4,6) 
[5 - 8] => 6 + (2,3,4,6) 
[9 - 12] => 6*2 + (2,3,4,6) 
... 

予測可能なパターンで値が繰り返されることに注意してください。行を取得するには、cの値をとり、セットsの長さで割ります（nと呼んでください）。設定インデックスは、cとnのmodです。この問題で使用されている1の索引付けのために1を引く。

row = floor((c-1)/n) 
column = `(c-1) % n` 
result = (a*b)*row + s(column) 

のPythonのimpl：

a = 2000 
b = 3000 
c = 100000 
s = list(set([a*i for i in range(1, b+1)] + [b*i for i in range(1, a+1)])) 
print((((c-1)//len(s)) * (a*b)) + s[(c - 1)%len(s)])