首页 > 其他分享 >ABC-280解题报告

ABC-280解题报告

时间:2023-03-01 16:47:06浏览次数:53  
标签:ABC int ll mid long 解题 ans 280 now

D. Factorial and Multiple

题意:给你一个 \(k\),求最小的 \(n\) 使得 \(k|n!\)。\(k\le 10^{12}\)。

做法一

考虑将 \(k\) 分解质因数,对于每项 \(p^r\),都要求 \(n!\) 中含有至少 \(r\) 次 \(p\)。由于 \(n!\) 的质因数单调增加,所以可以二分。对于检查某个 \(n\) 是否满足条件,只需要看 \(n\) 以内有多少个 \(p\) 的倍数 + \(n\) 以内有多少个 \(p^2\) 的倍数……以此类推。对于每个 \(p^r\) 取对 \(n\) 限制最大的那个即可,最后可能剩下的一个 \(>\sqrt{n}\) 的质因数特判一下。时间复杂度 \(\sqrt{n}+\log^3(n)\)。

检查 \(n!\) 中 \(p\) 的次数使用的方法被称为“勒让德定理(Legendre's Formula)”,描述是: \(n!\) 中 \(p\) 的次数等于 \(\sum\limits_{k\ge 1} \left\lfloor\frac{n}{p^k}\right\rfloor\)。证明:首先对于所有的 \(p\) 的倍数都要计算一次贡献,为 \(\left\lfloor\frac{n}{p}\right\rfloor\);然后对于所有 \(p^2\) 的倍数,我们希望计算两次贡献,而当前只计算了一次,所以需要再加上 \(\left\lfloor\frac{n}{p^2}\right\rfloor\) 的贡献。以此类推得到上述结论。

勒让德定理有一个扩展形式,描述为:\(n!\) 中 \(p\) 的次数等于,\(n\) 减去“将 \(n\) 转化为 \(p\) 进制后的各位之和”,再除以 \(p-1\)。证明:容易发现 \(\left\lfloor\frac{n}{p}\right\rfloor\) 即为 \(n\) 在 \(p\) 进制下右移一位的结果,\(\left\lfloor\frac{n}{p^2}\right\rfloor\) 即为 \(n\) 在 \(p\) 进制下右移两位的结果,以此类推。故对于 \(n\) 的第 \(i\) 位(从低到高),它会分别在第 \(i-1,i-2,i-3,\cdots,0\) 位统计贡献,故第 \(i\) 位 \(e_i\) 造成的贡献为 \(\sum\limits_{j<i} e_i\cdot p^j=e_i\cdot \frac{p^i-1}{p-1}\),而总贡献即为每一位的贡献之和(\(x\) 为位数):

\[\frac{\sum\limits_{i=1}^{x}e_ip^i-\sum\limits_{i=1}^{x}e_i}{p-1}=\frac{(n-e_0)-(\sum\limits_{i=0}^x e_i-e_0)}{p-1}=\frac{n-\sum\limits_{i=0}^x e_i}{p-1} \]

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	int k,ans=0;
	cin>>k;
	for(int i=2;i*i<=k;i++) {
		if(k%i!=0) continue;
		int cnt=0,l=1,r=k;
		while(k%i==0) cnt++,k/=i;
		while(l<r) {
			int mid=(l+r)/2,now=0;
			for(int x=i;x<=mid;x*=i) {
				now+=mid/x;
				if(now>=cnt) break;
			}
			if(now>=cnt) r=mid;
			else l=mid+1;
		}
		ans=max(ans,l);
	}
	if(k!=1) ans=max(ans,k);
	cout<<ans<<endl;
	return 0;
}

这个做法有许多本质相同的变种,如:每次将 \(mid\text{/=}x\) 而不是 \(x\text{*=}i\);在外部二分,内部整体 check;check 时每步跳跃 \(i\) 地枚举阶乘等。

每次减小 \(mid\) By potato167

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t=1;
	//cin>>t;
	rep(i,0,t) solve();
}

void solve(){
	ll K;
	cin>>K;
	ll ans=0;
	auto p=Prime_factorization(K);
	for(auto x:p){
		ll l=1,r=K;
		while(r-l>1){
			ll med=(r+l)/2;
			ll D=med;
			ll tmp=0;
			while(med){
				med/=x.first;
				tmp+=med;
			}
			if(tmp<x.second) l=D;
			else r=D;
		}
		chmax(ans,r);
	}
	cout<<ans<<"\n";
}

外部二分,整体 check By IH19980412

void solve(){
	int k;cin>>k;
	auto p = pollard_rho_fast::factorize2(k);
	int lb=0, ub = 1e12+5;
	while(ub-lb>1){
		int mid=(lb+ub)/2;
		for(auto x:p){
			int num=x.a;
			int cnt=x.b;
			int t=0;
			int now=mid;
			while(now){
				t += now / num;
				now /= num;
			}
			if(t < cnt) goto fail;
		}
		ub=mid;continue;
		fail:;lb=mid;
	}
	o(ub);
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int t; t = 1; //cin >> t;
	while(t--) solve();
}

每步跳跃枚举阶乘 By ygussany

#include <stdio.h>

void chmax(long long* a, long long b)
{
	if (*a < b) *a = b;
}

int main()
{
	long long K;
	scanf("%lld", &K);

	int j;
	long long i, ans = 1, tmp, tmpp;
	for (i = 2; i * i <= K; i++) {
		if (K % i != 0) continue;
		for (j = 0; K % i == 0; j++, K /= i);
		for (tmp = i; 1; tmp += i) {
			for (tmpp = tmp / i, j--; tmpp % i == 0; tmpp /= i, j--);
			if (j <= 0) break;
		}
		chmax(&ans, tmp);
	}
	if (K >= 2) chmax(&ans, K);
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

提前跑一层最后再加回来 By daisybunny

#include<bits/stdc++.h>
using namespace std;
map<long long,long long> mp;
long long k;
vector<long long> v;
long long ma;
void fjzys(long long a)
{
	long long x=a;
	for(long long t=2;t*t<=a;t++)
	{
		//cout<<t*t<<endl;
		if(x%t==0)
			v.push_back(t);
		while(x%t==0)
		{
			mp[t]++;
			x/=t;
			//cout<<t<<" ";
		}
	}
	if(x!=1)
	{
		v.push_back(x);
		mp[x]++;
	}
}
int main()
{
	cin>>k;
	fjzys(k);
	for(long long t=0;t<v.size();t++)
	{
		long long sum=0;
		for(long long i=1;;i++)
		{
			long long x=i;
			long long b=0;
			while(x%v[t]==0)
			{
				x/=v[t];
				b++;
			}
			sum+=b+1;//提前跑了一层
			if(sum>=mp[v[t]])
			{
				ma=max(i*v[t],ma);//补回来
				break;
			}
		}
	}
	cout<<ma;
	return 0;
}

做法二

考虑直接枚举 \(n\),维护当前 \(n!\) 对 \(k\) 的模数,直到第一次为 \(0\) 时满足条件。这个做法直接写肯定会超时,但注意到当 \(n\) 比较大时就将大部分情况覆盖地非常全了,唯一一种没有覆盖到的情况只能是 \(k\) 有一个非常大的质因子。此时该质因子只能出现一次(因为 \(>\sqrt{k}\)),所以答案的 \(n=\) 该质因子。

正确性证明:

假设 \(k\) 在 \(\sqrt{k}\) 以内的某个质因子 \(p^r\),则在枚举 \(n\) 时至少会在每个 \(p\) 的倍数被覆盖一次,所以 \(n\) 保证正确性的枚举上界为最大的 \(pr\)。有 \(r=\log_p(k)\),所以枚举上界为 \(p\log_p(k)\),其在 \(p>2\) 时单调递增,所以最坏情况有 \(\begin{cases}p=2,r=\log_2(k)\\p=\sqrt{k},r=2\end{cases}\),所以枚举到 \(2\sqrt{k}\) 即可保证正确性。

另一种证法:在 \(10^4\sim 10^6\) 内的质因数最多出现两个,所以到 \(2\times 10^6\) 即可保证正确性;在 \(10^4\) 以内的质因数最多也只能有不超过 \(100\) 个,所以到 \(10^6\) 就能保证正确性

By noimi

int main() {
    LL(k);
    auto f = factor(k);
    ll ma = 0;
    rep(i, si(f)) { chmax(ma, f[i].fi); }

    ll now = 1;
    rep(i, 1, ten(8)) {
        now = now * i % k;
        if(!now) {
            OUT(i);
            exit(0);
        }
    }
    OUT(ma);
}

还有一种不同的实现,每次枚举到一个数时将它能覆盖到的 \(k\) 的质因数覆盖掉,即将 \(k\text{/=}\gcd(i,k)\)。当积累的覆盖足够多,直到能将 \(k\) 的所有质因数全部覆盖完,就达到了 \(i!\) 是 \(k\) 的倍数的目标。

By physharp

k=int(input())
import math
for n in range(1,2000001):
  k//=math.gcd(k,n)
  if k<2: exit(print(n))
print(k)

标签:ABC,int,ll,mid,long,解题,ans,280,now
From: https://www.cnblogs.com/cxm1024/p/17168384.html

相关文章

  • ABC-279解题报告
    比赛传送门C.RANDOM题意:给你两个01矩阵\(S,T\),问是否可以将\(S\)以列为单位重新排列得到\(T\)。判断\(S,T\)的每列是否可以一一对应即可做法一以列为单位......
  • ABC-288解题报告
    比赛传送门D.RangeAddQuery题意:有一个序列\(A\)和正整数\(k\),每次询问给定\(l,r\),你可以在\([l,r]\)内选择一段长度为\(k\)的子段,统一加减,问是否能将\([l,r......
  • ABC-271解题报告
    C.Manga题意:有一本书有\(n\)卷,你需要从第一卷开始依次看,一旦没有某一卷就停止。在看之前你可以进行若干次操作,每次卖掉任意两卷并买新的任意一卷。问操作结束后最多能......
  • AGC-059解题报告
    比赛传送门A.MyLastABCProblem题意:有一个只含ABC字符串\(s\),每次询问一段区间\([l,r]\),问至少需要多少次操作能将这段区间变得完全相同。每次操作可以选一段区......
  • ABC275D-Yet-Another-Recursive-Function题解
    题目传送门题意:定义一个\(\mathbb{N}\to\mathbb{N}\)的函数\(f(x)=\begin{cases}1&x=0\\f(\lfloor\frac{x}{2}\rfloor)+f(\lfloor\frac{x}{3}\rfloor)&\text{otherwis......
  • CFR-826-Div-3解题报告
    F.Multi-ColoredSegments题意:数轴上有\(n\)个线段,每个区间有一个颜色\(c\),对于每个线段,求与它颜色不同的线段中与它的最短距离。距离定义为两个线段中的点集最近的......
  • CFR-832-Div-2解题报告
    B.BANBAN题意:给你一个\(n\),生成一个字符串为BAN重复\(n\)遍。每次操作可以选择两个位置进行交换,问至少多少次交换后可以使该串不存在BAN的子序列。输出方案。......
  • CFR-755-Div-2解题报告
    比赛传送门赛时AC三道,补题做出一道。A.MathematicalAddition{%noteinfono-iconProblem%}给你两个正整数\(u,v\),求一对合法的\(x,y\)使得\(\frac{x}{u}+\fra......
  • CFR-844-Div-1-2解题报告
    比赛传送门A.ParallelProjection题意:有一个\(w\timesd\timesh\)的长方体,顶面和底面有两个点,只能走直线且不能穿过长方体,求最短距离。显然曼哈顿距离必须要走。......
  • CFR-745-Div-2解题报告
    没打比赛,赛后做出3道。这场比赛题目质量很高,非常巧妙。A.CQXYMCountPermutations\(Problem\)求有多少\(2n\)的排列满足存在超过\(n\)个\(i\)使得\(p_i<p_{i+......