luogu5316

P5316 恋恋的数学题

题目背景

恋恋是个可爱的女孩子，最近她沉迷了做数学题。

题目描述

现在恋恋正在处理的题目十分简单：现在有

按照套路，恋恋非常想复原出那

输入输出格式

输入格式：

第一行，两个整数

接下来

第一行， $frac{k(k-1)}2$

第二行， $frac{k(k-1)}2$

输出格式：

输出

输入输出样例

输入样例#1：复制

1 3
4 6 2
48 144 36

输出样例#1：复制

16 12 18

输入样例#2：复制

2 4
4 2 4 6 4 2
48 144 16 36 12 36
1 1 1 1 2 1 
56 63 70 72 40 90

输出样例#2：复制

16 12 18 4
7 8 9 10

说明

保证奇数测试点中，第一行（gcd行）数据均为

测试点编号		输入整数不超过
1,2	2
3,4	2
5,6	2	$10^7107$
7,8	3
9,10	3	$10^7107$
11,12	3	$10^{14}1014$
13,14	4
15,16	4	$10^7107$
17,18	4	$10^{14}1014$
19,20	4	$10^{18}1018$

保证数据有解，

SPJ按照每组中的正确比例给分，但如果TLE、RE等会导致无输出而爆零

sol：这个k非常小，所以那个乱序就是让我们爆搜用的，知道了每个数字两两之间的gcd和lcm就很好做了，因为gcd(a,b)*lcm(a,b)=a*b,所以我们就得到了每个数字两两之间的乘积易知a=sqrt((a*b)*(a*c)/(b*c))

这样就可以轻松做出k=3的数据了，然后我暂时还没想出k=4怎么做（感觉用一模一样的方法可以过720*720*4*玄学）

但是k=4还没写。。。所以只有60pts

Ps :丧心病狂的出题人卡long long ,甚至直接__int128有些地方也会爆

感觉洛谷完全做不动了

#include <bits/stdc++.h>
using namespace std;
//typedef long long ll;
inline __int128 read()
{
    __int128 s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')

#define G1 Gcd[1]
#define G2 Gcd[2]
#define G3 Gcd[3]
#define G4 Gcd[4]
#define G5 Gcd[5]
#define G6 Gcd[6]
#define L1 Lcm[1]
#define L2 Lcm[2]
#define L3 Lcm[3]
#define L4 Lcm[4]
#define L5 Lcm[5]
#define L6 Lcm[6]
int T,n;
__int128 Gcd[10],Lcm[10];

inline __int128 Div(__int128 a,__int128 b,__int128 c); //a*b/c
inline __int128 Sqrt(__int128 x);
inline __int128 gcd(__int128 a,__int128 b);
inline __int128 lcm(__int128 a,__int128 b);
inline bool Judge(__int128 a,__int128 b,__int128 c); //a,b,c是否满足条件 

inline __int128 Div(__int128 a,__int128 b,__int128 c) //a*b/c
{
    __int128 g1=gcd(a,c),g2=c/g1;
    return (a/g1)*(b/g2);
}
inline __int128 Sqrt(__int128 x)
{
    __int128 l=1,r=1e18;
    while(l<=r)
    {
        __int128 mid=(l+r)>>1;
        if(mid*mid==x) return mid;
        else if(mid*mid<x) l=mid+1;
        else r=mid-1;
    }
    return 0;
}
inline __int128 gcd(__int128 a,__int128 b)
{
    return (!b)?(a):(gcd(b,a%b));
}
inline __int128 lcm(__int128 a,__int128 b)
{
    return Div(a,b,gcd(a,b));
}
inline bool Judge(__int128 a,__int128 b,__int128 c)
{
    if((gcd(a,b)!=G1)||(lcm(a,b)!=L1)) return false;
    if((gcd(a,c)!=G2)||(lcm(a,c)!=L2)) return false;
    if((gcd(b,c)!=G3)||(lcm(b,c)!=L3)) return false;
    return true;
}
namespace n2
{
    inline void Solve()
    {
        while(T--)
        {
            W(read()); Wl(read());
        }
    }
}
namespace n3
{
    inline void Solve()
    {
        int i;
        while(T--)
        {
            for(i=1;i<=3;i++) R(Gcd[i]);
            for(i=1;i<=3;i++) R(Lcm[i]);
            sort(Gcd+1,Gcd+4);
            do
            {
                sort(Lcm+1,Lcm+4);
                do
                {
                    __int128 ab=G1*L1,ac=G2*L2,bc=G3*L3;
                    __int128 a2=Div(ab,ac,bc),b2=Div(ab,bc,ac),c2=Div(ac,bc,ab);
                    __int128 a=Sqrt(a2),b=Sqrt(b2),c=Sqrt(c2);
                    if((!a)||(!b)||(!c)) continue;
                    else if(Judge(a,b,c))
                    {
                        W(a); W(b); Wl(c); goto loop;
                    }
                }while(next_permutation(Lcm+1,Lcm+4));
            }while(next_permutation(Gcd+1,Gcd+4));
            loop:;
        }
    }
}
namespace n4
{
    inline void Solve()
    {
        
    }
}
int main()
{
    R(T); R(n);
    if(n==2) n2::Solve();
    else if(n==3) n3::Solve();
    else if(n==4) n4::Solve();
    return 0;
}
/*
input
1 3
4 6 2
48 144 36
output
16 12 18
*/

View Code