用户工具

站点工具


2020-2021:teams:wangzai_milk:20200718比赛记录

这是本文档旧的修订版!


2020牛客暑期多校训练营(第三场)

比赛情况

题号 A B C D E F G H I J K L
状态 O O O O O O Ø - - - - O

O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试

比赛时间

2020-07-18 12:00-17:00

题解

F - Fraction Construction Problem

给 $1 \le a,b \le 2e6$,问是否存在 $1 \le c,d,e,f \le 4e12$ 且 $d,f \lt b$,使得 $\frac cd - \frac ef = \frac ab$。

分类讨论一下,如果 $a$ 和 $b$ 不互质可以很容易构造出来;如果互质,分解 $b$,如果 $b$ 只有一种质因子则不存在,否则令 $d$ 和 $f$ 为 $b$ 的两个互质的因数,然后通分,分子就是个拓欧。

code

code

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ALL(x) (x).begin(),(x).end()
#define ll long long
#define ull unsigned long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 2e6+5;
const ll B = 4e12;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
 
bool vis[maxn];
vector<int> prime;
inline ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
inline ll exgcd(ll a,ll b,ll &x,ll &y)
{
    ll d;
    if(!b) d=a,x=1,y=0;
    else {d=exgcd(b,a%b,y,x);y-=a/b*x;}
    return d;
}
void init()
{
    int n = 2e6;
    rep(i,2,n){
        if(!vis[i]) prime.pb(i);
        for(ll j=(ll)i*i;j<=n;j+=i) vis[j] = 1;
    }
}
int main()
{
    int _; init();
    ll a,b,c,d,e,f;
    for(scanf("%d",&_);_;_--){
        scanf("%lld%lld",&a,&b);
        if(b==1){
            printf("-1 -1 -1 -1\n");
        }else{
            ll k = gcd(a,b);
            if(k > 1){
                a/=k,b/=k;
                d = b,f = b;
                c = a+1,e = 1;
                printf("%lld %lld %lld %lld\n",c,d,e,f); continue;
            }else{
                if(!vis[b]){ // ab互质且b为质数
                    printf("-1 -1 -1 -1\n"); continue;
                }
                for(int x:prime){
                    if(b%x==0){
                        d = 1;
                        while(b%x==0) d*=x,b/=x;
                        break;
                    }
                }
                if(b==1){   // 只有一种质因子
                    printf("-1 -1 -1 -1\n"); continue;
                }
                f = b;
                exgcd(f,d,c,e);
                if(c<0){
                    ll k = abs(c)/d+1;
                    c += k*d,e -= k*f;
                }
                printf("%lld %lld %lld %lld\n",c*a,d,-e*a,f);
            }
        }
    }
    return 0;
}


比赛总结与反思

2020-2021/teams/wangzai_milk/20200718比赛记录.1595088618.txt.gz · 最后更改: 2020/07/19 00:10 由 wzx27