70分求助 #7/8 RE #9 WA

Dragonkiss @ 2023-07-31 23:54:54

#include<iostream>
using namespace std;
int main()
{
    int x0,y0;
    cin>>x0>>y0;
    int p[10000]={0},q[10000]={0};
    int num=0;
    int k=y0/x0;
    for(int i=1;i<=k;i++)
    {
        p[i]=i*x0;
        q[i]=i*x0;//创建两个3 6 9 ... 60的数组（x0的1 2 3...k倍）
    }
    for(int i=1;i<=k;i++)
    {
        for(int j=i;j<=k;j++)
        {
        if(y0%q[j]==0 && y0%p[i]==0)//判断数组内的数是否为y0的约数，排除如27 33等数
           {
            int z=y0/q[j];//60/15=4
            int x=y0/p[i];//60/12=5
            int u;
            for(int h=2;h<=x;h++)
            {
                if(z%h ==0 && x%h==0)
                {
                    break;
                }
                u=h;//判断y0是否为这两个数的最小公倍数
            }    

            if(u==x)//如果是最小公倍数
            {
            int e=q[j]/x0;//15/3=5
            int f=p[i]/x0;//12/3=4
            num+=2;
            //cout<<p[i]<<" "<<q[j]<<"+"<<endl;
            for(int h=2;h<=f;h++)
            {
                if(e%h ==0 && f%h==0)
                {
                    num-=2;
                    //cout<<p[i]<<" "<<q[j]<<"-"<<endl;
                    break;
                }
            }            //判断x0是否是两个数的最大公约数

            }
          }
        }
    }
    cout<<num;
}

by ybc2025chenyuyang @ 2023-08-01 00:00:03

@Dragonkiss 首先,你的数组开小了,应当开100005 其次,你不怕超时吗?这道题开3重循环.

即使你把数组开大点,你还是得TLE...(

by Dragonkiss @ 2023-08-01 00:06:20

@ybc2025125chenyuyang 确实..改了后两个超时T T WA也没有改对 请问您觉得我这个思路有什么优化方式吗？

by Dragonkiss @ 2023-08-01 00:31:34

现在代码如下 不知道为什么总是会出现两个0 0的情况 就在最后num-2处理了，答案应该都是对的 3 60；2 100000；3 900；测试数据都是对的但不知道为什么总是RE

#include<iostream>
using namespace std;
int main()
{
    int x0,y0;
    cin>>x0>>y0;
    int p[100005]={0},q[100005]={0};
    int num=0;
    int k=y0/x0;
    int f=1;
    for(int i=1;i<=k;i++)
    {
        if(k%i==0)
        {
            p[f]=i*x0;
            q[f]=i*x0;
            f++;
        }//创建两个数组
    }
    for(int i=1;i<=f;i++)
    {
        for(int j=i;j<=f;j++)
        {

            int z=y0/q[j];//60/15=4
            int x=y0/p[i];//60/12=5
            int u=0;
            for(int h=2;h<=x;h++)
            {
                if(z%h ==0 && x%h==0)
                {
                    break;
                }
                u=h;//判断y0是否为这两个数的最小公倍数
            }    

            if(u==x)//如果是最小公倍数
            {
            int e=q[j]/x0;//15/3=5
            int f=p[i]/x0;//12/3=4
            num+=2;
            cout<<p[i]<<" "<<q[j]<<"+"<<endl;
            for(int h=2;h<=f;h++)
            {
                if(e%h ==0 && f%h==0)
                {
                    num-=2;
                    cout<<p[i]<<" "<<q[j]<<"删除"<<endl;
                    break;
                }
            }            //判断x0是否是两个数的最大公约数

            }

        }
    }
    cout<<num-2;
}

by Dragonkiss @ 2023-08-01 01:30:36

思路没问题（但纯编程fw） 改对了终于

#include <iostream>
using namespace std;
int main()
{
    int x0, y0;
    cin >> x0 >> y0;
    if (x0 > y0)
    {
        cout << 0;
    }
    else if (x0 == y0)
    {
        cout << 1;
    }
    else if (y0 % x0 != 0)
    {
        cout << 0;
    }
    else
    {
        int p[100005] = {0}, q[100005] = {0};
        int num = 0;
        int k = y0 / x0;
        int f = 1;
        for (int i = 1; i <= k; i++)
        {
            if (k % i == 0)
            {
                p[f] = i * x0;
                q[f] = i * x0;
                f++;
            } // 创建两个数组
        }
        for (int i = 1; i <= f - 1; i++)
        {
            for (int j = i; j <= f - 1; j++)
            {

                int z = y0 / q[j]; // 60/15=4
                int x = y0 / p[i]; // 60/12=5
                int u = 0;
                for (int h = 2; h <= x; h++)
                {
                    if (z % h == 0 && x % h == 0)
                    {
                        break;
                    }
                    u = h; // 判断y0是否为这两个数的最小公倍数
                }

                int flag = 0; // 标志变量
                if (u == x)   // 如果是最小公倍数,判断x0是否是两个数的最大公约数
                {
                    int e = q[j] / x0; // 15/3=5
                    int f = p[i] / x0; // 12/3=4
                    for (int h = 2; h <= f; h++)
                    {
                        if (e % h == 0 && f % h == 0)
                        {
                            flag = 1; // 若存在f是e和h的公约数，则flag变为1
                            // cout<<p[i]<<" "<<q[j]<<"删除"<<endl;
                            break;
                        }
                    }
                    if (flag == 0)
                    {
                        // cout<<p[i]<<" "<<q[j]<<"正确"<<endl;
                        num += 2;
                    }
                    // cout<<"本轮num:"<<num<<endl;
                }
            }
        }
        cout << num;
    }
    return 0;
}

by Samuume @ 2023-08-09 21:29:51

@Dragonkiss 以后少用iostream，多用用bits/stdc++.h用处大

by Dragonkiss @ 2023-08-10 21:49:24

@WSCU_DZ_XM 好的 感谢