【算法每日一练]-数论（保姆级教程 篇3 ）#越狱 #找朋友 #全部相同 #方形 #tax

目录

今日知识点：

基于涂色问题的组合数

求所有数的最大公约数

阶乘质因数分解

哥德巴赫猜想

越狱

找朋友

全部相同?

方形

tax

---

????????

????????

越狱

监狱有n个房间，每个房间关一个犯人，有m种宗教，一个犯人信仰一种。如果相邻的房间犯人信仰同一种宗教就会越狱。问有多少种可能发生越狱

输入
2 3
输出：6

思路：
直接反正做：把总情况数减去不会发生越狱的情况数。

总情况数是m^n。

不会发生越狱的情况数是m*(m-1)^(n-1)。因为只有第一个人可以随意信仰宗教，其余人只需要和上一个人的不同即可。反正就是高中学过的涂色问题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1007;
ll ans,m,n;

ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1){
			res=res*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int main(){
	cin>>m>>n;
	ans=qpow(m,n)-qpow(m-1,n-1)*m%mod;
	ans=(ans%mod+mod)%mod;
	cout<<ans<<'\n';
}

????????

?????????

找朋友

n个人分成m组，每组至少一个人，在比赛结束的时候同一组的人两两之间就会成为朋友，不同的分组方案得到的朋友对数不同。求出最小和最大的朋友对数。

输入：
5 1
输出:10 10

思路：

很明显最大的朋友对数，一定是其余组只有一个人，剩余的人都在一个组中。

最小的朋友对数，一定是每组人数尽量相同。即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,maxn,minn,tmp,tmp2;

int main(){
	cin>>n>>m;
	tmp=n-(m-1);
	maxn=tmp*(tmp-1)/2;
	tmp=n/m;
	tmp2=n%m;
	minn=(tmp*(tmp-1))/2*(m-tmp2)+(tmp*(tmp+1))/2*tmp2;
	cout<<minn<<" "<<maxn;
		
}

????????

????????

全部相同?

一共有n个整数组成的数组a1,a2,……现任取一个正整数k进行下面操作：

从数列中取出一个数ai减去k。一共进行了若干次(可能是0次)操作后，数列中所有的数都相等了。请你找出k的最大可能取值。（如果k可以任意大输出-1）

输入? ? ? ? ? ? ? ? ? ? ? ? ?输出：2
3? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1?
6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1100? ? ? ? ??
1 5 3 1 1 5
8
-1 0 1 -1 0 1 -1 0
4?
100 -1000 -1000 -1000
?

思路：

很明显我们要把其余的数都变成最小的数。那么k必然是那些数的最大公约数才行。然后当原数据就已经完全相等的时候自然只需要操作0次就行，那么k可以任意大

#include <bits/stdc++.h>
using namespace std;
int t,n,a[50];

int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<n;i++)cin>>a[i];
		sort(a,a+n);//默认升序
		for(int i=1;i<n;i++){
			a[i]-=a[0];
		}
		if(a[n-1]==0){
			cout<<-1<<'\n';
			break;
		}
		int ans=gcd(a[1],a[2]);
		for(int i=3;i<n;i++)
			ans=gcd(ans,a[i]);
		cout<<ans<<'\n';
	}
}

????????

?????????

方形

思路：

只需要用上高中的知识不难发现是：C(m,m+n)。然后就是计算了。这里肯定是要用上高精度了?。

C(m,m+n)=(m+n)! / (m)! / (m+n-m)!=(m+n)…(n) / (m)!?

然后计算阶乘完全可以写成质因数分解的形式，然后高精度除法就被转化成了质因数的次方相减。

最后再进行高精度乘法即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,N2=105;
int n,m;
int fac[N],a[N2]={1},c[N2];

void clear(int c[]){
	for(int i=0;i<N2;i++)c[i]=0;
}
void multiply(int a[],int b,int c[]){//a*b=c
	clear(c);
	for(int i=0;i<N2;i++){
		c[i]+=a[i]*b;
		if(c[i]>=10){
			c[i+1]+=c[i]/10;
			c[i]%=10;
		}
	}
}

int main(){
	cin>>m>>n;
	n=n+m;//求C(m,m+n)
	for(int i=n-m+1;i<=n;i++){//计算分子的阶乘
		int tmp=i;//对每个数进行质因数分解
		for(int j=2;j*j<=tmp;j++){
			while(tmp%j==0){
				fac[j]++;
				tmp/=j;
			}
		}
		if(tmp>1)
			fac[tmp]++;
	}
	for(int i=1;i<=m;i++){
		int tmp=i;
		for(int j=2;j*j<=tmp;j++){
			while(tmp%j==0){
				fac[j]--;
				tmp/=j;
			}
		}
		if(tmp>1)
			fac[tmp]--;
	}
	for(int i=2;i<N;i++){
		while(fac[i]--){
			multiply(a,i,c);
			memcpy(a,c,sizeof(c));
		}
	}
	for(int i=99;i>=0;i--){
		if(i%10==0)
			cout<<a[i]<<'\n';
		else
			cout<<a[i];
	}
	return 0;
}

????????

?????????

tax

一个人前来交税，交的税钱是收入n的最大因子(不等于n的最大因数)，但是现在这个人为了避税，把前拆成几份(每份至少为2)，使得交税最少，输出税钱。

输入4

输出2

思路：

首先这个数据量极大，没法模拟！然后我们也不需要模拟

根据哥德巴赫猜想，偶数都可以分解成两个质数，那么大于2的偶数只需要交2即可

如果这个是质数，那么交1即可

如果这个数是奇数，那么必然可以拆成一个质数和一个偶数，也就是交3即可

#include <bits/stdc++.h>
using namespace std;

int prime(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

int main(){
	int n;cin>>n;
	if(n%2==0&&n>2){cout<<2;return 0;}
	if(n==2){cout<<1;return 0;}
	if(prime(n)){cout<<1;return 0;}
	if(n%2){cout<<3;return 0;}
}