首页 > 其他分享 >数论专题练习

数论专题练习

时间：2023-07-08 21:45:51浏览次数：49  
标签：prime 专题 数论 ll 练习 long int num ans

数论专题练习

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问题

题意：

标签：prime,专题,数论,ll,练习,long,int,num,ans
From： https://www.cnblogs.com/xxcdsg/p/17537932.html

相关文章

  • 整除分块（数论分块）
    整除分块是为了解决一个整除的求和的问题：sum(floor(n/i))(1<=i<=n) ，如果直接暴力计算复杂度O（n），但整除分块的复杂度为O（2sqrt(n)），其中的2为常数，可以忽略，那么复杂度为O(sqrt(n))下面给出整除分块的模板代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;ll......
  • 牛客练习赛113 D 小红的数组操作(hard version)
    题目要求求出最小的总代价使得平均数为整数，转换式子可得实际就是求出a,b使得(a*x-b*y+sum)%n==0且a*p+b*q要最小，平均值的为sum/n,因此对sum进行操作使其成为n的倍数即可(a*x-b*y+sum)%n==0=>((a*x+sum)%n-b*y%n)%n==0因为(a*x+sum)%n<n,b*y%n<n,因此要想二者差求余数为0一定为(......
  • 20230708练习总结
    CF1785DWoodenSpoon为了方便，将题目中的大小关系反转一下。这是一个\(n+1\)层的满二叉树，第\(i\)层每个点都是\(2^{n-i+1}\)个人中的胜者。如果从下往上dp，需要记录胜利者编号和得到木勺者编号，会爆掉。那么从上往下dp。设\(dp_{i,j}\)表示第\(i\)层\(j\)胜利随即......
  • python基础列表专题
    用[]可以创建列表列表可以包含各种类型且可嵌套通过切片和索引访问列表元素添加元素删除元素列表不适合频繁插入，因为每插入一个，元素都会后移动深度拷贝列表是可以改变的不可哈希的，所以不可以做字典的键 ......
  • # Python_函数专题（一）
    目录函数基础基础函数调用参数返回值变量承接print定义函数定义函数的格式函数嵌套函数调用死循环函数参数单参数双参数报错指定参数类型函数文档注释函数返回值Return定义带有返回值的参数返回多个值函数基础基础函数的基础理论函数，即一段具有特定功能的代码块调用函数，即......
  • 数论
    算法记号\(a\modp\)：\(a\)除\(p\)的余数，等于\(a-p\times\lfloor\frac{a}{p}\rfloor\)。\(a\midb\)：\(a\)整除\(b\)即\(a\)是\(b\)的因数。素数判定试除法对于任意整数\(n\)，它的因数\(d,\frac{n}{d}\)总是成对出现，所以可以枚举\([2,\sqrt{n}]\)内的数......
  • 【专题】2022中国新能源汽车内容生态趋势洞察报告PDF合集分享（附原数据表）
    车内容的网络用户和中国新能源汽车企业为研究对象，选择了与新能源汽车有关的网络内容（图片，直播，视频，用户评价），并与中国新能源汽车产业的生产和销售数据相结合，展开了一项调查（查看文末了解报告PDF版本免费获取方式）。当前，新能源汽车已经成为推动汽车行业销量的主要动力，同时，国内自主品牌......
  • 数据结构练习
    数据结构练习[NOI2021]密码箱这么说Quack大爷就有队爷水平了首先考虑\(f\)是个线性变换这里对于\(\dfrac{x}{y}\rightarrow\dfrac{y}{x}+a_i\),第\(i\)个元素可以用矩阵表示\[\left[\begin{matrix}x&y\\0&0\\\end{matrix}\right]\times\left[\begin{matrix}......
  • 循环语句-while-练习题
    1'''2练习while循环3其实就是练习手感，不停的敲4'''56'''71.打印星号(三⻆形)8*9**10***11****12*****13找规律，弄懂需求：5行5列，只显示了column<=row。显示的内容是*14解决：2个循环搞定15'''1617row=118whi......
  • wpf小说阅读器 ----wpf练习demo
    1.登录窗口布局<Grid><Grid.ColumnDefinitions><ColumnDefinition/><ColumnDefinitionWidth="2*"/></Grid.ColumnDefinitions><Border><Border.Backgro......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99