【唯一分解】A因子

╰半夏微凉° 2024-03-17 17:33 70阅读 0赞

[A-因子\_Wannafly挑战赛25 (nowcoder.com)][A-_Wannafly_25 _nowcoder.com]

题意：

![9471ada1ff164aac9bff961980e03ec4.png][]

思路：

![35408d541b734c648a67d2cb233b69e7.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N,K;
    int len=0;
    int vis[mxn],prime[mxn];
    
    void P_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    int calc(int x){
        int tn=N;
        int res=0;
        while(tn){
            res+=tn/x;
            tn/=x;
        }
        return res;
    }
    void solve(){
        cin>>N>>K;
        int ans=1e18;
        for(int i=2;i*i<=K;i++){
            if(K%i==0){
                int cnt=0;
                while(K%i==0){
                    cnt++;
                    K/=i;
                }
                int t=calc(i);
                ans=min(ans,t/cnt);
            }
        }
        if(K!=1) ans=min(ans,calc(K));
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        P_init(1e4);
        while(__--)solve();return 0;
    }

[A-_Wannafly_25 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/197/A
[9471ada1ff164aac9bff961980e03ec4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/278ca625889247f98c461cce77a61a46.png
[35408d541b734c648a67d2cb233b69e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/dadc281d2593417e9c6fc50f1b0dca61.png

发表评论取消回复

表情：

评论列表（有 0 条评论，70人围观）

还没有评论，来说两句吧...

相关阅读

相关【唯一分解】A因子

[A-因子\_Wannafly挑战赛25 (nowcoder.com)][A-_Wannafly_25 _nowcoder.com] 题意： ![9471ada1ff164

╰半夏微凉°/ 2024年03月17日 17:33/ 0 赞/ 71 阅读

相关 Trailing Zeroes (I) LightOJ - 1028(唯一分解因子个数）

Trailing Zeroes (I) LightOJ - 1028 题目链接：[https://vjudge.net/problem/LightOJ-1028][htt

深碍√TFBOYSˉ_/ 2023年08月17日 15:40/ 0 赞/ 97 阅读

相关整数因子分解

文章目录题目描述样例输入样例输出解题代码 -------------------- 题目描述整数因子分解问题。

爱被打了一巴掌/ 2022年12月28日 14:16/ 0 赞/ 174 阅读

相关分解素因子

分解素因子 Time Limit: 1500ms Memory limit: 10000K 有疑问？点这里^\_^ 题目描述假设x是一个正整数，它的值不超过

￡神魔★判官ぃ/ 2022年08月10日 05:52/ 0 赞/ 189 阅读

相关整数因子分解问题

问题描述：大于1的正整数n可以分解为n=x1\x2\…\xn。例如，当n=12时，共有以下8种分解方法： 12=12 12=6\2 12

淩亂°似流年/ 2022年08月02日 06:41/ 0 赞/ 194 阅读

相关牛课等式（唯一分解定理求因子个数）

[点击打开链接][Link 1] include<cstdio> include<cmath> using namespace std;

喜欢ヅ旅行/ 2022年05月28日 01:48/ 0 赞/ 194 阅读

相关质因子分解

概念：所谓质因子分解是将一个正整数n写成一个或多个质数的乘积形式。例如：6=2\3，180=2\2\3\3\5，也可以写成指数形式，例如 180=2^2\3^2\5^1；

男娘i/ 2022年04月24日 08:48/ 0 赞/ 229 阅读

相关整数因子分解问题(分治)

整数因子分解问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Probl

深藏阁楼爱情的钟/ 2022年02月17日 11:44/ 0 赞/ 223 阅读

相关 1722 整数因子分解问题

整数因子分解问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 大于1的正整数n可以

╰+哭是因爲堅強的太久メ/ 2022年02月17日 06:46/ 0 赞/ 185 阅读

相关整数因子分解问题

整数因子分解问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Probl

柔光的暖阳◎/ 2022年02月15日 02:06/ 0 赞/ 327 阅读