CF（比賽加練習補題）

第一次熬夜打CF （打CF遊戲都沒有熬夜打過嗚嗚嗚）

踏上了cf上分掉分 之旅，這裡記錄一下一些好的題目加以練習鍛煉思維

2020.12.20開坑

2020.12.20 求質因數的方法

CF1444A Division

#include<bits/stdc++.h>
#define ll long long
#define fp(i,a,b) for(int i=a;i<=b;i++)
#define sfp(i,a,b) for(int i=a;i<b;i++)
const ll N = 1e6+10;
using namespace std;

ll t;
ll p,q,cnt;
ll a[N],cnt1[N],cnt2[N];
void solve()
{
	cin>>p>>q;
	if(p%q!=0) cout<<p<<endl;
	else
	{
		cnt=0;
		ll b=sqrt(q);
		ll 	P=p;
		//求q的質因數用a[]存起來，用cnt1存含有的個數
		fp(i,2,b)
		{
			if(q%i==0) a[++cnt]=i;
			while(q%i==0)
			{
				cnt1[cnt]++;
				q/=i;
			}
		}
		if(q>1)    //如果q本身就是質數
		{
			a[++cnt]=q;
			cnt1[cnt]=1;
		}
		//OVER
		fp(i,1,cnt)
		{
			while(p%a[i]==0)
			{
				cnt2[i]++;
				p/=a[i];
			}
		}
		ll ans=0;
		fp(i,1,cnt)
		{
			ll c=cnt2[i]-cnt1[i]+1;
			ll sum=1;
			for(int j=1;j<=c;j++) sum*=a[i];
			//sum=pow(a[i],c);
			ans=max(ans,P/sum);
		}
		cout<<ans<<endl;
		fp(i,1,cnt) cnt1[i]=0,cnt2[i]=0;
	}
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin>>t;
	while(t--) solve();
}
           

求數的質因數打方法在代碼裡面（注釋）

該題的思路是找當p%q==0時，也就是q為p一個因子時，p中其他因子，且不能被q整除的最大值。

先将q拆除質因數表示的形式 如12=223(兩個2和一個3),由于q為p因數，故p也含有這些質因數，将相同質因數的個數相減+1去枚舉求出最大的因子。

P=12=223, Q=6=23 p2-q2+1=2, 22=4 有點抽象

2021.1.6 掉大分

Codeforces Round #694 (Div. 2) B題補題

點我~

#include<bits/stdc++.h>
#define int ll
#define ll long long
#define fp for(int i=1;i<=n;i++)
#define sfp for(int i=0;i<x;i++)
const ll N = 2e7+5;
using namespace std;
 
ll n,x;
ll a[N];
void solve() {
	cin>>n>>x;
	ll sum=0;
	fp {
		cin>>a[i];
		sum+=a[i];
	}
	ll tt=x;
	fp{
		if(a[i]%tt==0) sum+=a[i];
		else break;
		if(i==n)
		{
			tt*=x;
			i=0;
		}
	}
	cout<<sum<<endl; 
}
 
ll t;
 
signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin>>t;
	while(t--)
		solve();
	return 0;
}
           

參考巨佬得思路

2中的數組為[4,6,8,2]，x為2，之後數組内産生的新元素為[2,2,3,3,4,4,1,1,1,1,1,1]，再把它們合并一下就成了[4,6,8,2,4]，發現每次循環，隻需要将除數擴大一倍，再跑一遍，隻要除不了就直接跳出即可