489div2-Problem B

给定gcd和lcm反求a和b；

坑比较多，卡了这题，很闹心。 一是题读错了，忘了考虑gcd=lcm的情况。 二是有gcd与lcm不成一对，本身就不存在的情况。

最终改完的代码如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100000 + 5

long long x,y,mul;
long long l,r;
long long ans;

int main() {

    cin>>l>>r>>x>>y;
    if(x == y &&  x>=l && x<=r ) {
        cout<<"1"<<endl;
        return 0;
    }

    mul = x*y ;
    long long maxx=y/x;
    long long sqr=sqrt(mul);

    ans = 0;
    if(y % x ==0) {
        for(long long ga=1; ga * ga <= maxx; ga++) {
            if(maxx % ga == 0) {
                long long gb = maxx/ga;
                if(ga*x>=l&&ga*x<=r
                 &&gb*x>=l&&gb*x<=r
                 &&__gcd(ga,gb) == 1 
                 && gb > ga)
                    ans++;
            }
        }
        cout<<ans*2<<endl;
    } 
    else {
        cout<<"0"<<endl;
    }
    return 0;
}

找到了一个比较简洁的实现。 首先把合适的a和b存入vector，然后再运算一次即可。

虽然实现速度不如上面的代码，但是好在能避开很多坑。 尤其最后的判断条件直接用了a*b/gcd（a，b）=y；

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define MOD 1000000007

using namespace std;

ll l, r, x, y, d;
set<ll> uf;

bool good(ll i) {
    return (i >= l && i <= r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> l >> r >> x >> y;
    d = x*y;
    int ans = 0;
    for(ll i=1; i*i<=y; i++) {
        if(y % i == 0) {
            uf.insert(i);
            uf.insert(y / i);
        }
    }
    for(auto a : uf) {
        for(auto b : uf) {
            if(good(a) && good(b) && __gcd(a,b) == x && a*b/__gcd(a,b) == y) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

简单排序+贪心。 一开始用vector做不知道为什么超时。 后改贪心，其中两种情况没有返回 i=j-1；卡了半天。

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
#define MAXN 100010

int Micro[MAXN*2];
int n,K;
int tim=0;

bool cmp(int a, int b)
{
    return a<b;
}

int main()
{

    cin>>n>>K;
    for(int i=0;i<n;i++)
        cin>>Micro[i];

    sort(Micro,Micro + n,cmp);

    int flag = 0;
    int ans=0;

    for(int i=0;i<n;i++)
    {
        int j=i+1;

        while( Micro[i] == Micro[j] ){
            j++;

            if( j == n) i=j-1;
            
            if(Micro[j] <= Micro[i] + K && Micro[i]!=Micro[j] && j<n ){
               for(int t=i;t<j-1;t++)  Micro[t]=0;
            i=j-1;
            }

            else if (Micro[j] > Micro[i] + K)   i = j-1;
        }

        if(Micro[j] <= Micro[i] + K && j<n ){
            Micro[i] = 0;
        }
    }

    for(int i=0;i<n;i++){
        if(Micro[i]!=0) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

参考其他代码，有直接用pos记录upper_loader返回值的做法。 另外没有清零，直接对答案进行记录。 代码简洁了很多。