Wannafly挑战赛25 A 因子数学

- 日理万妓 2021-12-21 15:37 211阅读 0赞

[题面][Link 1]

题意:令 X = n!,给定一大于1的正整数p,求一个k使得 p ^k | X 并且 p ^(k + 1) 不是X的因子,n,,p(1e18>=n>=1e4>=p>=2)

题解:我们要找得也就是k满足 x%(p^k)==0 同时 x%(p^k\*p)!=0 显然这样的k 就是x范围内最大的那个p的幂次 因为再乘个p肯定就超过x了

我们也许会首先想到,直接看x里有多少p的倍数就行了,但是很显然,对于样例p=12,有单独的因子3和4结合,因子2和6结合,也可以满足

所以我们显然对p进行处理 处理成p=2^x \* 3^y \* 5^z……

例如样例p=12 n=10000 p=2^2 \* 3

我们先统计n!里有多少个2

t=n/2+n/4+n/8+n/16……

而每个p需要2个2 所以 需要 t/2 个2^2

统计n!有多少个3

同理 o=n/3+n/9+n/27+n/81 需要o/1 个 3^1

t,o中最小的就是答案,p的最小幂次

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 long long n,p,k,sum,t,nn;
     4 int main()
     5 {
     6     cin>>n>>p;
     7     k=1e18;
     8     for (int i=2;i<=p;i++) 
     9         if (p%i==0)
    10         {
    11             nn=n;sum=0;
    12             while (nn)
    13             {
    14                 nn/=i;
    15                 sum+=nn;
    16             }
    17             t=0;
    18             while (p%i==0)
    19             {
    20                 p/=i;
    21                 t++;
    22             }                
    23             k=min(k,sum/t);
    24         }
    25     printf("%lld",k);
    26 }

转载于:https://www.cnblogs.com/qywhy/p/9728506.html

[Link 1]: https://www.nowcoder.com/acm/contest/197/A

发表评论取消回复

表情：

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

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

相关阅读

相关【裴属定理】Wannafly挑战赛22 A

[A-计数器\_Wannafly挑战赛22 (nowcoder.com)][A-_Wannafly_22 _nowcoder.com] 题意： ![4302eb25c979

「爱情、让人受尽委屈。」/ 2024年03月17日 16:07/ 0 赞/ 82 阅读

相关【二维属性+贪心+双指针】Wannafly 挑战赛15 A

[Wannafly挑战赛15\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][Wannafly_15_ACM_

你的名字/ 2024年03月17日 16:07/ 0 赞/ 77 阅读

相关 Wannafly 挑战赛5

A 题: 星神是来自宇宙的所以珂朵莉也是吧所以我就出了个题给你一个长为n的序列a，有n\(n+1)/2个子区间，问这些子区间里面和为完全平方数的子区间个数 in

柔情只为你懂/ 2022年06月03日 01:58/ 0 赞/ 321 阅读

相关 Wannafly挑战赛5 A.珂朵莉与宇宙

Wannafly挑战赛5 A.珂朵莉与宇宙题目描述星神是来自宇宙的所以珂朵莉也是吧所以我就出了个题

一时失言乱红尘/ 2022年06月02日 02:16/ 0 赞/ 205 阅读

相关 Wannafly挑战赛9

A 题目描述给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数输入描述: 第一行输入一个n

朱雀/ 2022年05月31日 01:54/ 0 赞/ 213 阅读

相关 Wannafly挑战赛11 -A 白兔的分身术

链接： [https://www.nowcoder.com/acm/contest/73/A][https_www.nowcoder.com_acm_contest_73_A]

ゞ浴缸里的玫瑰/ 2022年05月30日 12:37/ 0 赞/ 204 阅读

相关 Wannafly挑战赛21 C 大水题

题目链接：[点我][Link 1] 链接：https://www.nowcoder.com/acm/contest/159/C 来源：牛客网题目描述现在给你N

- 日理万妓/ 2022年05月17日 07:04/ 0 赞/ 215 阅读

相关 Wannafly挑战赛23 A ：字符串（尺取法）

[题目传送门][Link 1] 代码： include<bits/stdc++.h> using namespace std; cons

╰半夏微凉°/ 2022年05月14日 06:28/ 0 赞/ 184 阅读

相关 Wannafly挑战赛25 A 因子数学

[题面][Link 1] 题意:令 X = n!,给定一大于1的正整数p,求一个k使得 p ^k | X 并且 p ^(k + 1) 不是X的因子,n,,p(1e18>=n>

- 日理万妓/ 2021年12月21日 15:37/ 0 赞/ 212 阅读

相关牛客 Wannafly挑战赛24 A石子游戏(思维)

[题目链接][Link 1] 链接：[https://www.nowcoder.com/acm/contest/186/A][Link 1] 来源：牛客网 Alice

谁借莪１个温暖的怀抱￠/ 2021年09月16日 09:00/ 0 赞/ 338 阅读