Math ( 思维/数论 )

题目链接:https://codeforces.com/contest/1062/problem/B
题目大意:给定一个n,你有两种操作,乘以任意数(非零),开根(开根后要是整数),问最找那个能到达的最小值和操作的次数
解题思路:首先易得最小值是n的素因子之积,那么操作次数呢?
通过样例我们发现,每一次操作都可以让素因子的幂除以二,操作次数就是n的素因子的幂先通过乘到达就近的2的幂,然后通过开跟每次除二,又由于乘的数可以是若干个素因子的积,任何数都可以通过一次乘法使得每个素因子的幂是2的x次幂,由此可解。但是特别🐶的是有好多特殊的情况要考虑,比如n是1的时候就不要先乘2再除二了。。。感觉要不是cf可以看后台数据能卡我半天了。。
代码

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

int maxx;
int minn;
int cnt;

int main()
{
    int a;
    cin>>a;
    maxx=0;
    minn=0x3f3f3f3f;
    int ansa=1,ansb;
    for(int i=2; i<=1000000; i++)
    {
        cnt=0;
        if(a%i==0)
        {
            ansa*=i;
        }
        while(a%i==0)
        {
            cnt++;
            a/=i;
        }
        if(cnt!=0)
        {
            maxx=max(maxx,cnt);
            minn=min(minn,cnt);
        }
    }
    if(maxx==1||maxx==0)
    {
        cout<<ansa<<" 0"<<endl;
        return 0;
    }
    int k=0,pp=1;
    while(1)
    {
        k++;
        pp*=2;
        if(pp>=maxx)
        {
            break;
        }
    }
    ansb=k;
    if(minn!=maxx||maxx!=pp)
    {
        ansb++;
    }
    cout<<ansa<<" "<<ansb<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注