love is possible
2022-05-15 09:53
采纳率: 75%
浏览 7

关于#PTV#的问题,如何解决?(语言-c语言)

已知正整数 a0,a1,b0,b1,设某未知正整数 x 满足:

1. x 和 a0 的最大公约数是 a1
2. x 和 b0 的最小公倍数是 b1

求解满足条件的 x 的个数。请你帮助他编程求解这个问题。

对于 100%的数据,保证有 1≤a0,a1,b0,b1≤2,000,000,000。

输入格式:
第一行为一个正整数 n,表示有 n 组输入数据。n≤2000

接下来的 n 行每行一组输入数据,为四个正整数 a0,a1,b0,b1,之间用一个空格隔开。

输出格式:
共n 行。每组输入数据的输出结果占一行,为一个整数。 对于每组数据:若不存在这样的 x,请输出 0; 若存在这样的 x,请输出满足条件的 x 的个数;

输入样例:
在这里给出一组输入。例如:

2
41 1 96 288
95 1 37 1776
输出样例:
在这里给出相应的输出。例如:

6
2
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C (gcc)








1
#include<stdio.h>
2
#include<math.h>
3
int gmd(int x,int y)
4
{
5
int m, n, a, b;
6
m=x;
7
n=y;
8
while(y!=0)
9
{
10
a=x%y;
11
x=y;
12
y=a;
13
}
14
return x;
为什么会运行超时?如何更改?

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

  • love is possible 2022-05-15 09:56

    这是我运行的,超时了

    #include<stdio.h>
    2
    #include<math.h>
    3
    int gmd(int x,int y)
    4
    {
    5
    int m, n, a, b;
    6
    m=x;
    7
    n=y;
    8
    while(y!=0)
    9
    {
    10
    a=x%y;
    11
    x=y;
    12
    y=a;
    13
    }
    14
    return x;
    15
    }
    16
    int main()
    17
    {
    18
    int i,j,k;
    19
    int a0,a1,b0,b1,x,flag1=0,r1,r2;
    20
    int n;
    21
    scanf("%d",&n);
    22
    for(k=1;k<=n;k++)
    23
    {
    24
    flag1=0;
    25
    scanf("%d %d %d %d",&a0,&a1,&b0,&b1);
    26
    r1=a0/a1;r2= b1/b0;
    27
    for(i=1;i*i<=b1;i++)
    28
    {
    29

    30
    if(gmd(i/a1,r1)==1&&gmd(r2,b1/i)==1)
    31
    flag1=flag1+1;
    32
    }
    33
    printf("%d\n",flag1);
    34
    }
    35
    return 0;
    36
    }

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题