How to AK NOI Online2022-junior

· · 个人记录

前言：

因为 T2忘了写一种情况，导致 170 \rightarrow 110，痛失前 25%，

T1-kingdom

太水了，不写。

T2-math

题目解法：

设 gcd(x,y) = d

x=pd y=qd z=x \cdot y \cdot \gcd(x,y) = pd \cdot qd \cdot d = pqd^3

因为 p 与 q 互质，p^2 与 q 互质

d^2 = gcd(p^2d^2,qd^2) = gcd(x^2,\frac{z}{x}) d = \sqrt{gcd(x^2,\frac{z}{x})} y = \frac{\frac{z}{x}}{d} = \frac{\frac{z}{x}}{\sqrt{gcd(x^2,\frac{z}{x})}}

现在求出了 y 那么代入检验即可

\color{green}\text{AC 代码：}

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    int t;
    ll x,z;
    inline ll read()
    {
        ll x=0,f=1;
        char ch=getchar();
        while(!isdigit(ch))
        {
            if(ch=='-')f=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*f;
    }
    inline void write(ll x)
    {
        if(x<0)
        {
            x=-x;
            putchar('-');
        }
        if(x>=10)write(x/10);
        putchar(x%10^48);
    }
    inline ll gcd(ll a,ll b)
    {
        return !b?a:gcd(b,a%b);
    }
    void main()
    {
        scanf("%d",&t);
        ll y;
        while(t--)
        {
            x=read();
            z=read();
            if(z%x!=0)
            {
                write(-1);
                putchar('\n');
                continue;
            }
            y=(z/x)/sqrt(gcd(x*x,z/x));
            if(x*y*gcd(x,y)!=z)
            {
                write(-1);
                putchar('\n');
                continue;
            }
            write(y);
            putchar('\n');
        }
        #ifndef ONLINE_JUDGE
        system("pause");
        #endif
    }
}
int main()
{
    Main::main();
    return 0;
}

T3-string

咕咕咕