查找可以被a或b整除的第N个数字

-2

给定两个数字a和b，您必须找到第n个数字，它可以被a或b整除。查找可以被a或b整除的第N个数字

输入：第一行由整数T组成，表示测试用例的数量。第二行包含三个整数a，b和N.

输出：对于每个测试用例，请在一行中打印第N个号码。

限制条件： 1≤t≤10^5 1≤a,b≤10^4 1≤N≤10^9

采样输入

1 
2 3 10

样本输出

说明其是被2整除或3中的数字：2,3 ，4,6,8,9,10 ，12,14,15和10号数为15

我的代码（C）中是：

#include<stdio.h> 

int main() 
{ 
    long long int i,a,b,n,j,c=0,small; 
    scanf("%lld",&i); 
    while(i--) 
    { 
     scanf("%lld%lld%lld",&a,&b,&n); 
     if(a==b) 
     { 
      printf("%lld ",a*n); 
      return 0; 
     } 
     else 
     { 
      if(a>b) 
       small = b ; 
      else 
       small = a ; 
      for(j=small;1;j++) 
      { 
       if(j%a==0 || j%b==0) 
        c++ ; 
       if(c==n) 
        break ; 
      } 
     } 
     printf("%lld",j); 
    } 
    return 0 ; 
}

但它不是有效时（即需要超过1秒）上输入：1000 10000 100000000

来源

2017-09-10 Ashu_1907

你能给这个问题的链接？ –

@ MD.KhairulBasar Aquestion必须是独立的。不要求链接，但要在**文本中说明**。 – Olaf

如果代码是正确的，这可能更适合代码审查，而不是堆栈溢出。 – Olaf

-1

您正在使用线性搜索其在最坏的情况下为O（n）的时间复杂度，因此它需要超过1秒或更多。你需要改善这个搜索时间。

您需要使用二进制搜索才能找到答案。使用PIE（包含 - 排除原理）计算从1到x有多少个数可以被a或b整除。现在，在的每一步中，二进制搜索计算可以由a或b整除多少个数字。当这个数字等于n时，返回并打印答案。这在最坏的情况下需要O（log n）个步骤。

#include<stdio.h> 
typedef long long LL; 

LL gcd(LL a, LL b) 
{ 
    if (a == 0) 
     return b; 
    return gcd(b % a, a); 
} 

LL BS(LL a, LL b, LL n) 
{ 
    LL high,low,mid,cnt,lcm; 
    low = 1; 
    high = 1e18; 
    lcm = (a * b)/gcd(a, b); 

    while(low <= high) 
    { 
     mid = (low + high)/2; 
     cnt = (mid/a) + (mid/b) - (mid/lcm); 

     if(cnt < n) 
      low = mid + 1; 
     if(cnt > n) 
      high = mid - 1; 
     if(cnt == n) 
      break; 
    } 
    while(mid % a && mid % b) 
     mid--; 
    return mid; 
} 

int main() 
{ 
    LL a,b,n,t; 
    scanf("%lld",&t); 
    while(t--) 
    { 
     scanf("%lld %lld %lld", &a, &b, &n); 
     printf("%lld\n", BS(a, b, n)); 
    } 
    return 0; 
}

来源

2017-09-10 12:22:22

为什么downvote？ –

对于mid来说，你需要检查mid是否可以被a或b整除。 –

@AshharJawaid是的。你是对的。感谢您指出了这一点。我已经更新了我的答案。 –

您不需要遍历所有数字。

外观期和涉及LCM（A，B）

例如您输入

1 
2 3 10

LCM（2,3） = 6

且顺序为2 3 4 6 6+2 6+3 6+4 6+6 6*2+2 ... =>每个周期的计数= 4

因此你可以找到第10个数字= 6 * floor（10/4）+ 3 * = 15。

*的是因为它是（10 MOD 4）个序列元素（让 = 0）

来源

2017-09-10 12:39:59

在这种情况下失败'1 1 1 1'。输出应该是 - '1'，但是你的输出 - '3'。 –

@ MD.KhairulBasar我已经更新了答案，使其更加清晰。 –

如果您发布了您提出的一般公式，而不是直接使用值进行评估，那将会更好。 –

查找可以被a或b整除的第N个数字

回答

相关问题