题解 CF1285C 【Fadi and LCM】

· · 题解

这道题是2020年1月10日CF比赛的C题（不用讲也都知道）

题目大意：

给你一个整数x，找出一对满足：

  1. 最小公约数为x
  2. 两个数中最大的数最小

（本人语文及其不好，看不懂还是看翻译吧！）

本人的想法

似乎许多大佬都是根号级算法。我在看题目的时候，最先想到的是暴力质因数分解

根据唯一定理 ，x=p1^a1 p2^a2 ...... * pk^ak

(我不会LaTeX，就将就一下吧）

那我们就将这k个数（将pi^ai看做一个数），分成两份，让分出来最大的数最小，就行了（若将pi^ai分成pi^(ai-k)和pi^k,最小公约数一定不是x，而两个数都选择x的因子，互质，就能满足最小）

代码实现

由于这是暴力+质因数分解，代码很好理解的

#include<cmath>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
//#define int long long
using namespace std;
const int MAXN=1005;
const int MAXM=1000005;
bool v[MAXM];  
int n,m,tot,ans1,ans2,a[MAXN],prime[MAXM];
inline int Max(int a,int b){return a<b?b:a;}
inline void primes(){
    memset(v,1,sizeof v);
    v[0]=v[1]=0;
    for(int i=2;i<=MAXM;i++){
        if(v[i]) prime[++m]=i;
        for(int j=1;j<=m;j++){
            if(i*prime[j]>MAXM) break;
            v[i*prime[j]]=0;
            if(i%prime[j]==0) break;
        }
    }
    return;
}
inline int Quickpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a;
        b/=2;a*=a;
    }
    return ans;
}
inline void work(int x){
    for(register int i=1;i<=m&&prime[i]*prime[i]<=x;++i)
        if(x%prime[i]==0){
            int sum=0;
            while(x%prime[i]==0){
                sum++;
                x/=prime[i];
            }
            a[++tot]=Quickpow(prime[i],sum);
        }
    if(x>1) a[++tot]=x;
}
inline void dfs(int i,int s1){
    if(i>tot){
        int Maxn=Max(s1,n/s1);
        //printf("%lld\n",Maxn);
        if(Maxn<ans2) ans1=n/Maxn,ans2=Maxn;
        return ;
    }
    dfs(i+1,s1);
    dfs(i+1,s1*a[i]);
}
template <typename T> void in(register T& a){
    register T x=0,f=1;
    register char c=getchar();
    while(!isdigit(c)){
        c=='-'?f=-1:f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c = getchar();
    }
    a=x*f;
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ans1=ans2=999999999999;
    in(n);
    primes();
    work(n);
    dfs(1,1);
    printf("%lld %lld",ans1,ans2);
    return o;
}