526互联

数论专题练习

发布时间 2023-07-08 21:37:47作者: xxcdsg

数论专题练习

A - Beautiful Numbers

题意：输入a，b，n，求只包含a，b的n位数并且n位之和为a或b的数量

  • 枚举a和b的数量，判断它们的和是否为一个good_number，然后用组合数(详见数论的组合数)求和
#include<bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
const int MAXN = 1e6 + 10;
#define ll long long
int a,b,n;
bool good_number(int x)
{
	while(x)
	{
		if(x%10 != a && x%10 != b)
		return false;
		x/=10;
	}
	return true;
}
ll ny[MAXN];
void pre_ny()
{
    ny[1] = 1;
    for(int i = 2;i <= n;i++){
        ny[i] = (ll)(p - p / i)*ny[p % i] % p;//p - p / i是为了防止负数 
    }
}
ll jcny[MAXN];
void pre_jcny()
{
    jcny[0] = jcny[1] = 1;
    for(int i = 2;i <= n;i++){
        jcny[i] = (jcny[i - 1] * ny[i]) % p;
    }
}
ll jc[MAXN];
void pre_jc()
{
    jc[1] = 1;
    for(int i = 2;i <= n;i++){
        jc[i] = (jc[i - 1] * i) % p;
    }
}
ll C(ll n,ll m)
{
	return (((jc[n]*jcny[m])%p)*jcny[n-m])%p;
}
int main()
{
	cin >> a >> b >> n;
	pre_ny();pre_jcny();pre_jc();
	long long ans = 0;
	for(int i = 0;i <= n;i++)
	{
		if(good_number(a*i+b*(n - i)))
		{
			ans = (ans + C(n,i)) % p;
		}
	}
	cout << ans;
}

B - Fedya and Maths

题意：求\((1^n+2^n+3^n+4^n)mod\ 5\)的值

  • 找规律
  • \(1^n\ mod\ 5\)永远是1
  • \(2^n\ mod\ 5\)为2，4，3，1，2；四个一循环
  • \(3^n\ mod\ 5\)为3，4，2，1，3；四个一循环
  • \(4^n\ mod\ 5\)为4，1，4，1，4；两个一循环
  • 所以\((1^n+2^n+3^n+4^n)mod\ 5\)为0，0，0，4，0；四个一循环
  • 又100及以上部分都被4整除所以不考虑，那只要考虑最后两位是否为4的倍数即可
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string str;cin >> str;
	int num = 0,end = str.size() - 1;
	num = str[end] - '0';
	if(str.size() > 1)
	num += (str[end - 1] - '0') * 10;
	if(num % 4 == 0)
	cout << 4;
	else
	cout << 0;
}

C - Iterated Linear Function

题意：求ax+b进行n次后的结果

化简

\[a^nx+b\sum_{i = 1}^{n} a^x \]

注意等比数列求和公式中p不等于1

注意%的位置以免越界

#include<bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
#define ll long long
ll qpow(ll x,ll n)
{
	ll ans = 1;
	while(n){
		if(n&1) ans = (ans*x)%p;
		x=(x*x)%p;
		n>>=1;
	}
	return ans;
}
ll fmx(ll x)
{
	return qpow(x,p-2);
}
ll sum_mul(ll a1,ll n,ll q)
{
	return ((((qpow(q,n) + p - 1) % p) * fmx(q - 1) % p) * a1) % p;
}
int main()
{
	ll a,b,n,x;cin >> a >> b >> n >> x;
	if(a == 1)
	cout << (x+(n%p)*b)%p;
	else
	cout << (((qpow(a,n)*x) % p) + sum_mul(b,n,a))%p;
}

D - k-rounding

题意：求最小的以\(10^k\)为一个因子的能被n整除的数

即\(10^k\)与n的最小公倍数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b)
{
	if(b == 0) return a;
	else return gcd(b,a%b);
}
int main()
{
	ll n,k;cin >> n >> k;
	ll t = 1;
	while(k--)
	t*=10;
	cout << (n*t)/gcd(n,t);
}

E - 同余方程

题意：求最小的正逆元

即求方程\(ax+by=1\)，x的最小正整数解

而拓展欧几里得算法就可以实现这个功能

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
	exgcd(b,a%b,x,y);
	int xx = y;
	y = x - (a/b)*y;
	x = xx;
	return;
}
int main()
{
	ll a,b,x,y;cin >> a >> b;
	exgcd(a,b,x,y);
	cout << (x+b)%b;
}

F - 小凯的疑惑

题意：求\(ax+by=c\)在a，b都是正整数且\(gcd(a,b)=1\)的情况下，最大的c使得式子无解

赛瓦维斯特定理：已知\(a,b\)为大于1的正整数,\(gcd(a,b)=1\),则使不定方程\(ax+by=C\)不存在非负整数解的最大整数\(C=a×b−a−b\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll a,b;cin >> a >> b;
	cout << a*b-a-b;
}

G - Cheerleaders

题意：N*M大的足球场，4边必须站人，一共有k个人，问一共有多少种站法

利用容斥原理，4边都站人的情况等于所以情况减去一条边不占人的情况再加上两条边不站人的情况再减去三条边不站人的情况再加入四条边都不站人的情况

正常就枚举这四条边的状态就好

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int p = 1e6 + 7;
ll C[501][501]={0};
void pre_C()
{
	C[0][0] = C[1][1] = C[1][0] = 1;
	for(int i = 2;i <= 500;i++)
	{
		C[i][0] = 1;
		for(int j = 1;j <= i;j++)
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j])%p;
	}
}
int main()
{
	pre_C();
	int t;cin >> t;
	for(int q = 1;q <= t;q++)
	{
		ll n,m,k;cin >> n >> m >> k;
		ll ans = 0;
		for(int i = 0;i <= 15;i++)
		{
			int num = 0,ii = i,nn = n,mm = m;
			while(ii)
			{
				if(ii&1)
				{
					num++;
					nn--;
				}
				swap(nn,mm);
				ii >>= 1;
			}
			if(num%2 == 0)
			ans=(ans+C[nn*mm][k])%p;
			else
			ans=(ans-C[nn*mm][k]+p)%p;
		}
		cout <<"Case "<< q << ": " << ans << endl;
	}
}

当然也可以直接写

n-=2,m-=2;
ll ans = 0;
ans = C[(n+2)*(m+2)][k] - 2*(C[(n+1)*(m+2)][k]+C[(n+2)*(m+1)][k]) + (C[n*(m+2)][k]+4*C[(n+1)*(m+1)][k]+C[(n+2)*m][k])-2*(C[n*(m+1)][k]+C[(n+1)*m][k])+C[n*m][k];
while(ans<0)
ans+=p;
ans%=p;

H - 青蛙的约会

题意：一个长为L的环，两个青蛙分别从x，y的初始点同向出发，速度分别是m，n请问最短需要多少时间才能相遇（坐标完全相同，时间为正整数）

思路：根据题意可列出式子\(x+mt=y+nt\pmod l\)

化简\((m-n)t=y-x\pmod l\)

根据同余方程的性质可得\((m-n)t+lk=y-x\)

又根据拓展欧几里得定理可得\((m-n)t'+lk'=gcd(m-n,l)\)的解

如果\(y-x\)是\(gcd(m-n,l)\)的整数倍就说明有解，并且特解为\(t=((y-x)/gcd(m-n,l))*t'\)

又根据\(lcm(m-n,l)/(m-n)\)个\(t\)可以替换\(lcm(m-n,l)/l\)个\(k\)，就可以得出最小的\(t\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll tgcd;
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		tgcd = a;
		return;
	}
	exgcd(b,a%b,x,y);
	ll xx = y;
	y = x - (a/b)*y;
	x = xx;
	return;
}
int main()
{
	ll x,y,m,n,l;cin >> x >> y >> m >> n >> l;
	ll a = m - n,b = l,t,k;
	exgcd(a,b,t,k);
	if((y-x)%tgcd != 0)
	cout << "Impossible";
	else
	{
		int num = (y-x)/tgcd;
		t = num*t;
		ll lcm = (a/tgcd)*b;
		ll tt = abs(lcm/a);
		t = (t%tt + tt)%tt;
		cout << t;
	}
}

I - 跳蚤

题意：有n+1个数，其中最后一个数为最大的m，令它们的最大公因数为1，请问有多少种排列方式

  • 容斥原理再现，首先直接直接求答案比较困难，所以我们求最大公因数不为1的情况
  • 这样我们就要先分解m的质因数，然后枚举最大公约数为某个质因数的倍数
  • 根据容斥原理，还要考虑最大公约数为两个质因数的倍数的情况
  • 以此类推，有\(2^{cnt-1}\)种情况
  • 注意，此题中m可以很大，所以要用优化后的分解质因数的函数，即\(i*i<=m\)(别问，问就是超时)
#include<iostream>
using namespace std;
#define ll long long
ll prime[100],cnt;
ll qpow(ll x,ll n)
{
	ll ans = 1;
	while(n)
	{
		if(n&1) ans*=x;
		x*=x;
		n>>=1;
	}
	return ans;
}
void fzys(ll m)
{
	cnt = 1;
	for(ll i = 2;i*i <= m;i++)
	{
		if(m%i==0)
		{
			prime[cnt++]=i;
			while(m%i==0)
			m/=i;
		}
		i++;
	}
	if(m != 1)
	prime[cnt++]=m;
}
int main()
{
	ll n,m;cin >> n >> m;
	ll ans = qpow(m,n);
	fzys(m);
	for(int i = 1;i < (1 << (cnt - 1));i++)//枚举状态
	{
		int ii = i;
		int num = 0,p = 1;
		ll x = 1;
		while(ii)
		{
			if(ii&1)
			{
				num++;x*=prime[p];
			}
			p++;
			ii >>= 1;
		}
		if(num%2==1) ans-=qpow(m/x,n);
		else ans+=qpow(m/x,n);
	}
	cout << ans;
}

J - Combinations

题意：精确计算一百以内的组合数

思路：高精度加杨辉三角

#include<iostream>
using namespace std;
int C[101][101][200] = {0};
void add(int i,int j)
{
	for(int k = 0;k <= 198;k++)
	{
		C[i][j][k] += C[i-1][j][k]+C[i-1][j-1][k];
		C[i][j][k+1] = C[i][j][k]/10;
		C[i][j][k] %= 10;
	}
}
void putout(int n,int m)
{
	bool f = false;
	for(int i = 198;i >= 1;i--)
	{
		if(f||C[n][m][i])
		{
			f=true;
			cout << C[n][m][i];
		}
	}
	cout << C[n][m][0];
}
void build()
{
	C[0][0][0]=C[1][1][0]=C[1][0][0]=1;
	for(int i = 2;i <= 100;i++)
	{
		C[i][0][0] = 1;
		for(int j = 1;j <= i;j++)
		add(i,j);
	}
}
int main()
{
	ios::sync_with_stdio(false);//写了using namespace std;
	build();
	int n,m;cin >> n >> m;
	while(n != 0||m != 0)
	{
		cout << n << " things taken " << m << " at a time is ";
		putout(n,m);
		cout << " exactly."<<endl;
		cin >> n >> m;
	}
}

K - The Balance

题意：两种物品，重量分别为a,b，分别取x和y个，让它们能称出重量c，问x+y最小时x，y分别为多少

  • 用拓展欧几里得先算出\(ax+by=gcd(a,b)\)的一个特解，然后乘上倍数推出\(ax+by=c\)的特解
  • 取x最小和y最小时的特解，哪个小取哪个
#include<iostream>
using namespace std;
#define ll long long
ll gcd;
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		gcd = a;
		return;
	}
	exgcd(b,a%b,x,y);
	ll xx = y;
	y = x - (a/b)*y;
	x = xx;
	return;
}
int main()
{
	ll a,b,t;cin >> a >> b >> t;
	while(a!=0||b!=0||t!=0)
	{
		ll x,y;
		exgcd(a,b,x,y);
		ll lcm = a*b/gcd;
		ll tx = lcm/a,ty = lcm/b;
		x = (t/gcd)*x,y = (t/gcd)*y;
		ll x1 = (x%tx+tx)%tx;
		ll y1 = y - (x1-x)/tx*ty;
		ll y2 = (y%ty+ty)%ty;
		ll x2 = x - (y2-y)/ty*tx;
		if(abs(x1)+abs(y1) < abs(x2) + abs(y2))
		{
			x = abs(x1),y = abs(y1);
		}
		else
		{
			x = abs(x2),y = abs(y2);
		}
		cout << abs(x) << ' ' << abs(y) << endl;
		cin >> a >> b >> t;
	}
}

L - Goldbach's Conjecture

题意：分解一个大于4的数为两个质数，如果有多个解取相差最大的

思路：简简单单一个素数筛，简简单单一个枚举

#include<iostream>
using namespace std;
const int MAXN = 1e6 + 10;
bool unprime[MAXN];
int prime[100000];
void pre_prime()
{
	int i;
	for(i = 2;i*i <= MAXN-1;i++)
	{
		if(!unprime[i])
		{
			prime[++prime[0]]=i;
			int ii = i*2;
			while(ii<=MAXN-1)
			{
				unprime[ii]=1;
				ii += i;
			}
		}
	}
	while(i<=MAXN-1)
	{
		if(!unprime[i])
			prime[++prime[0]]=i;
		i++;
	}
}
int main()
{
	pre_prime();
	int n;cin >> n;
	while(n!=0)
	{
		bool flag = false;
		for(int i = 1;i <= prime[0] && n >= prime[i]*2;i++)
		{
			if(!unprime[n-prime[i]])
			{
				flag = true;
				cout << n << " = " << prime[i] << " + " << n - prime[i] << endl;
				break;
			}
		}
		if(!flag)
		cout << "Goldbach's conjecture is wrong." << endl;
		cin >> n;
	}
}

M - Prime Distance

题意：经典区间筛问题为什么换个编译器就能过呀WC，我真TM服了

  • 注意循环变量也要开long long，不然可能爆
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
const int MAXN = 50000,MAXM = 1e6 + 10;
bool a_unprime[MAXN],b_unprime[MAXM];
ll a_prime[10000],b_prime[100000];
void a_find_prime()
{
	int i;
	for(i = 2;i*i <= 49999;i++)
	{
		if(!a_unprime[i])
		{
			a_prime[++a_prime[0]] = i;
			ll p = (i << 1);
			while(p <= 49999)
			{
				a_unprime[p] = 1;
				p += i;
			}
		}
	}
	while(i <= 49999)
	{
		if(!a_unprime[i])
		a_prime[++a_prime[0]] = i;
		i++;
	}
}
void b_find_prime(ll l,ll r)
{
	if(l < 2)
	l=2;
	b_prime[0] = 0;
	memset(b_unprime,0,sizeof(b_unprime));
	for(ll i = 1;i <= a_prime[0];i++)
	{
		ll p;
		if(l%a_prime[i] == 0)
		p = l;
		else
		p = (l/a_prime[i]+1)*a_prime[i];
		if(a_prime[i] >= l)
		p <<= 1;
		while(p <= r)
		{
			b_unprime[p-l] = 1;
			p += a_prime[i];
		}
	}
	for(ll i = l;i <= r;i++)
	{
		if(!b_unprime[i-l])
		b_prime[++b_prime[0]] = i;
	}
}
int main()
{
	a_find_prime();
	ll l,u;
	while(~scanf("%lld %lld",&l,&u))
	{
		b_find_prime(l,u);
		if(b_prime[0] < 2)
		cout << "There are no adjacent primes." << endl;
		else
		{
			ll ma = 2,mi = 2;
			for(int i = 3;i <= b_prime[0];i++)
			{
				if(b_prime[i]-b_prime[i-1]>b_prime[ma]-b_prime[ma-1])
				ma = i;
				if(b_prime[i]-b_prime[i-1]<b_prime[mi]-b_prime[mi-1])
				mi = i;
			}
			cout << b_prime[mi-1] << ',' << b_prime[mi] << " are closest, " << b_prime[ma-1] << ',' << b_prime[ma] << " are most distant." << endl;
		}
	}
}

N - Happy 2006

题意：给出m和k，求第k个\(gcd(x,m)=1\)，x的值

思路：首先要求出小于m的与m互素的数的数量num，然后用k/m求出多少组，和k%m求出第几个

关于求num值的方法

  • 1.利用容斥原理：先将m分解成质因数，用容斥原理求num
  • 2.利用欧拉函数
  • 容斥原理：
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
const int MAXM = 1e6+10;
ll num;
bool un_prime[MAXM];
ll a_prime[100000],b_prime[10000];
int gcd(int a,int b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
void pre_prime()
{
	for(int i = 2;i <= 1000000;i++)
	{
		if(!un_prime[i])
		{
			a_prime[++a_prime[0]] = i;
			ll ii = (i << 1);
			while(ii <= 1000000)
			{
				un_prime[ii] = 1;
				ii += i;
			}
		}
	}
}
void find(ll m)
{
	b_prime[0] = 0;
	num = m;
	ll mm = m;
	for(int i = 1;i <= a_prime[0] && mm >= a_prime[i];i++)
	{
		if(mm % a_prime[i] == 0)
		{
			b_prime[++b_prime[0]] = a_prime[i];
			while(mm % a_prime[i] == 0)
			mm /= a_prime[i];
		}
	}
	for(int i = 1;i < (1 << b_prime[0]);i++)
	{
		ll ii = i;
		ll x = 1,p = 1,t = 0;
		while(ii)
		{
			if(ii&1)
			{
				t++;
				x*=b_prime[p];
			}
			p++;
			ii >>= 1;
		}
		if(t%2) num-=m/x;
		else num+=m/x;
	}
}
int main()
{
	ll m,k;
	pre_prime();
	while(~scanf("%lld %lld",&m,&k))
	{
		num = 0;
		find(m);
		ll mul = k/num;
		if(k%num==0)
			mul--;	
		else
			num = k%num;
		ll res = 0;
		while(num)
		{
			res++;
			if(gcd(res,m)==1)
			num--;
		}
		cout << res+mul*m << endl;
	}
}
  • 欧拉函数：
#include<iostream>
using namespace std;
#define ll long long
ll f_ol(ll x)
{
	ll ans = x;
	for(int i = 2;i*i <= x;i++)
	{
		if(x%i==0)
		{
			ans = ans/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ans = ans/x*(x-1);
	return ans;
}
ll gcd(ll a,ll b)
{
	if(b == 0) return a;
	else return gcd(b,a%b);
}
int main()
{
	ll m,k;
	while(~scanf("%lld %lld",&m,&k))
	{
		ll num = f_ol(m),ans;
		if(k%num == 0)
		{
			ans = (k/num-1)*m;
		}
		else
		{
			ans = k/num*m;
			num = k%num;
		}
		ll t = 0;
		while(num)
		{
			t++;
			if(gcd(t,m)==1)
			num--;
		}
		cout << ans + t << endl;
	}
}

O - Blocks

题意：n个方块，填四种颜色，要让其中两种颜色的数量都是偶数，问有多少种方法

思路：先将n个方块分成2t部分和n-2t部分，其中2t部分分成两个偶数颜色，那么假设这2t前2t-1随机放这两种颜色，那么2t放的颜色一定是确定的，才能使这两种颜色的数量都是偶数

因此可能的数量就为\(C_{n}^{2t}2^{n-2t}2^{2t-1}=C_{n}^{2t}2^{n-1}\)，又由于偶组合数之和等于奇组合数等于\(2^{n-1}\)，所以求和就为\(2^{2n-2}\)

但是发现当\(t=0\)时\(2^{2t-1}=1/2\)但我们要的是1，所以还要加上一个\(2^{n-1}\)

#include<iostream>
using namespace std;
#define ll long long
const int p = 1e4 + 7;
ll qpow(ll x,ll n)
{
	ll ans = 1;
	while(n)
	{
		if(n&1) ans=(ans*x)%p;
		x = (x*x)%p;
		n >>= 1;
	}
	return ans;
}
int main()
{
	int t;cin >> t;
	while(t--)
	{
		ll x;cin >> x;
		cout << ((qpow(2,2*x-2))%p + qpow(2,x-1))%p << endl;
	}
}

P - 机器人走方格 V2

题意：n*m大小的方格，只能向下或向右走，求从左上走到右下一共有多少种方法

思路：必需要向下走m-1格，向右走n-1格才能到，求全排列，那就是\(C_{n+m-2}^{n-1}\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int p = 1e9 + 7,MAXN = 2e6 + 10;
ll ny[MAXN];
void pre_ny()
{
    ny[1] = 1;
    for(int i = 2;i <= MAXN - 1;i++){
        ny[i] = (ll)(p - p / i)*ny[p % i] % p;//p - p / i是为了防止负数 
    }
}
ll C(ll n,ll m)
{
	ll ans = 1;
	for(int i = 2;i <= n;i++)
	ans = (ans*i)%p;
	for(int i = 2;i <= m;i++)
	ans = (ans*ny[i])%p;
	for(int i = 2;i <= n - m;i++)
	ans = (ans*ny[i])%p;
	return ans;
}
int main()
{
	pre_ny();
	ll x,y;cin >> x >> y;
	x--,y--;
	cout << C(x+y,x);
}

Q - Biorhythms

为什么放一个完全没有用的数在前面？为什么？？？啊啊啊啊啊啊啊啊啊啊啊啊？

题意：三个高峰，分别23,28,33天出现一次，分别给出这一年出现高峰的日期，求d天之后第一个出现三个高峰在同一天的日期

思路：求解

\[\begin{cases} x\equiv{p}\pmod{23} \\ x\equiv{e}\pmod{28} \\ x\equiv{i}\pmod{33} \end{cases} \]

所以使用中国剩余定理

因为28和33不是质数，所以不能用费马小定理，要用拓展欧几里得定理算逆元

#include<iostream>
using namespace std;
#define ll long long
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b == 0)
	{
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int xx = y;
	y = x - (a/b)*y;
	x = xx;
	return;
}
int main()
{
	ll t;cin >> t;
	ll p,e,i,d;cin >> p >> e >> i >> d;
	ll a,b,c;exgcd(924,23,a,t),exgcd(759,28,b,t),exgcd(644,33,c,t);
	a = (a + 23) % 23,b = (b + 28) % 28,c = (c + 33) % 33;
	a *= 924,b *= 759,c *= 644;
	t = 0;
	while(p != -1 || e != -1 || i != -1 || d != -1)
	{
		t++;
		ll ans = (a*p+b*e+c*i+21252-d)%21252;
		if(ans == 0)
		ans = 21252;
		printf("Case %lld: the next triple peak occurs in %lld days.\n",t,ans);
		cin >> p >> e >> i >> d;
	}
}

R - X问题

题意：