D - Factorial and Multiple
数论
首先上这道题需要的数论知识：
n!的素因子分解中，n!=p1^a1 * p2^a2 * p3^a3 * ..... * pk^ak中
对于素因数pi，其对于的ai=n/pi+n/pi^2+n/pi^3+....直到n/pi^j==0为止
证明如下：
对于 n!= 1* 2 * 3* 4 * ...... * n
其中的数可以表达成： 1 2 3 ...pi ....2pi....n1pi....n，用变量num来记录n!钟表pi的个数
其中 n1*pi<=n && (n1+1)*pi>n
那么现在明显的pi个数为 n1, 且有 n1= n/pi ,所以 ans+=n1;
但是可能 n1>=pi,即会有 原来的序列可以表达成：
1 2 3...pi...2pi...3pi...pi*pi...2*pi*pi....3pi*pi.....n2*pi*pi...n
其中 n2*pi*pi<=n && （n2+1）*pi>n
其实这里的n2*pi*pi==上面的n1*pi，只是n1=n2*pi，那么在原来已经求得ans=n1的基础上，ans+=n1/pi
但是还可能n2>=pi,接下来的操作与上面相同，像递归一样
于是有：
对于素因数pi，其对于的ai=n/pi+n/pi^2+n/pi^3+....直到n/pi^j==0为止
题解：
然后再看题目
我们首先可以对K进行素数分解，O（sqrt(K)）
然后，对n进行二分求解，即l=1,r=k;进行二分查找，对于mid=(l+r)>>1,看一下mid！的全部素因数的幂 是否>=K的全部素因数的幂
如果>=说明 mid! % K==0，否则不是
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 typedef long long ll;
6 const int N = 1e7;
7 ll k, t;
8 int pos = 0;
9 ll p[N], a[N];
10 bool check(ll mid)
11 {
12 for (int i = 1; i <= pos; i++)
13 {
14 ll n = mid, prime = p[i], num = 0;
15 while (n)
16 {
17 num += n / prime;
18 n /= prime;
19 }
20 if (num < a[i])
21 return false;
22 }
23 return true;
24 }
25 int main()
26 {
27 cin >> k;
28 ll l = 1, r = k, ans;
29 for (ll i = 2; i * i <= k; i++)
30 {
31 if (k % i == 0)
32 {
33 p[++pos] = i;
34 while (k % i == 0)
35 {
36 a[pos]++;
37 k /= i;
38 }
39 }
40 }
41 if (k > 1)
42 {
43 p[++pos] = k;
44 a[pos]++;
45 }
46 /* for (int i = 1; i <= pos; i++)
47 cout << p[i] << " " << a[i] << endl;
48 */
49 while (l <= r)
50 {
51 ll mid = (l + r) >> 1;
52 if (check(mid))
53 {
54 ans = mid;
55 r = mid - 1;
56 }
57 else
58 l = mid + 1;
59 }
60 cout << ans;
61 return 0;
62 }
标签：AtCoder,Beginner,...,ll,ans,mid,280,n1,pi From： https://www.cnblogs.com/cilinmengye/p/16949992.html