【数论】三角关系

一个高中学长问的一道题,挺有意思的。也是简单数论

t1 T2

T2

根据同余的加性,(以下以=代替同余号)

由于a+b=b+c(%k),b=b(%k)

所以可以得到a=c(%k)

同理可以得到a=b=c(%k)

所以目标转化为找同余数。由于任意两个相加需要是K的倍数,所以他们的余数必须都为k/2或者0。

设余数为i,在k是偶数的时候余数可以是k/2和k,在k为奇数的时候i只能是k。

算出每组的个数,再组合数算一下。任意m个里取1个有m种排法,取2个有6*C(m,2)种,取3个有A(3,3)*C(m,3)种。答案就是他们加起来。由于解题的时候在上课,所以我并没有写代码,提问者照着我的思路写了,并且AC了…………

T3

是Java,把int改为long long就AC了… Read the rest

【数论】蓝桥杯历届试题 小数第n位

http://lx.lanqiao.cn/problem.page?gpid=T456

问题描述
  我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
  如果我们把有限小数的末尾加上无限多个0,它们就有了统一的形式。


  本题的任务是:在上面的约定下,求整数除法小数点后的第n位开始的3位数。
输入格式
  一行三个整数:a b n,用空格分开。a是被除数,b是除数,n是所求的小数后位置(0<a,b,n<1000000000)
输出格式
  一行3位数字,表示:a除以b,小数后第n位开始的3位数字。
样例输入
1 8 1
样例输出
125
样例输入
1 8 3
样例输出
500
样例输入
282866 999000 6
样例输出
914

考虑到n取1e10,double的精度肯定是不够的。所以把数字放大10^n+2倍%1000进行计算。但由于b和1000不一定互质,所以不一定找得到逆元。

这里介绍一个公式

$$\frac{a}{b} \mod p = \frac{a \mod b \times p}{b}$$

所以本题:

$$\frac{a}{b} \times 10^{n+2} \mod 10^3 = \frac{a \times 10^{n+2} \mod b \times 10^3}{b} $$

$$ = \frac{(a \mod b \times 10^3) \times (10^{n+2} \mod b \times 10^3)}{b} $$

n取1e10,所以快速幂一下。就做完了,简单数论

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,n,mod;
Read the rest

蓝桥杯历届试题 小计算器

http://lx.lanqiao.cn/problem.page?gpid=T459

问题描述
  模拟程序型计算器,依次输入指令,可能包含的指令有


  1. 数字:'NUM X',X为一个只包含大写字母和数字的字符串,表示一个当前进制的数
  2. 运算指令:'ADD','SUB','MUL','DIV','MOD',分别表示加减乘,除法取商,除法取余
  3. 进制转换指令:'CHANGE K',将当前进制转换为K进制(2≤K≤36)
  4. 输出指令:'EQUAL',以当前进制输出结果
  5. 重置指令:'CLEAR',清除当前数字


  指令按照以下规则给出:
  数字,运算指令不会连续给出,进制转换指令,输出指令,重置指令有可能连续给出
  运算指令后出现的第一个数字,表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
  重置指令后出现的第一个数字,表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
  进制转换指令可能出现在任何地方


  运算过程中中间变量均为非负整数,且小于2^63。
  以大写的'A'~'Z'表示10~35
输入格式
  第1行:1个n,表示指令数量
  第2..n+1行:每行给出一条指令。指令序列一定以'CLEAR'作为开始,并且满足指令规则
输出格式
  依次给出每一次'EQUAL'得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

按题意模拟就可以了。由于是整数,所以把所有进制化为十进制计算,省去了自己写运算的东西。输出的时候转再转换一下就可以了。有个坑点是在ADD等运算之间可能转换进制。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,char> eco;
map<char,ll> deco;
int k=10;
ll ans=0;
char num[99];
void init()
{
	for(ll i=0;i<=9;i++)
	{
		eco[i]=i+'0';
		deco[i+'0']=i;
	}
	for(ll i='A';i<='Z';i++)
	{
		eco[i-'A'+10]=i;
		deco[i]=i-'A'+10;
	}
}
ll getnum()
{
	
Read the rest

【二分图匹配-最小边覆盖】mz语考试

Description
jswf夺冠后
cc: tql
gj: tggl
mz:tlrxml
frz: bksjs
wjjj: whnzmqa
......
js: ??? 
js: nmflb

————节选自某次mz语等级测试

mz语等级测试即将到来。然而mz语十分难,用词灵活多变,导致作弊人数众多。而防止考生作弊的一个有效的途径是让考生之间保持一定的距离。

某考场有R(行)*C(列)个座位,坐在(r, c)的考生可能会看到(r,c-1)、(r,c+1)、(r-1,c-1)、(r-1,c+1)(即左、右、左前、右前)4个位置的考生的答案。

为了防止这种情况发生,就要保证一个考生周围的这4个位置中无其他考生。

而由于这个考场年久失修,有一些座位已经损坏,是无法使用的。

现在,fls想知道,在保证无人能看到别人答案的前提下,这个考场最多能安排多少名考生?

Input
多组数据

第一行有一个整数T(T<=30),代表数据组数。

对每组数据,第一行有两个整数R、C(1 <= R, C <= 50),表示考场规模。

接下来R行,每行有一个长度为C的字符串,描述考场内每个位置。'.'表示该位置可用,'x'则表示已损坏。

Output
对每组数据,输出该考场内最多能安排的考生数。

Sample Input
1
2 3
...
.x.
Sample Output
4

相隔两列的人是看不见对方的。所以把有冲突的座位连边即为二分图。

任意两个冲突的位置只能有一个地方坐人,即任意点只能有一条边相连。边数就是能坐下的人。转化为了最小边覆盖问题。

答案就是 点数-最大匹配数

注意link vis这些变量名有可能会与STL冲突

#include<vector>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string> 
using namespace std;
int dx[]={-1, 0, 1,-1,0,1};
int dy[]={-1,-1,-1, 1,1,1};
char tsr[55][55];
vector<int> G[3025];
int id[55][55];
int visa[3025]={0};
int linka[3025]={0};
int r,c;
int lig(int 
Read the rest

【计算几何-技巧】射击游戏

Description
js在ak了一套cf后,打开了一款新出的射击游戏。

这个射击游戏在一个二维平面进行,js控制的人物处于坐标原点(0,0)。平面上共有n只怪物,每个怪物所在的坐标为(x[i], y[i])。js进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。

而高贵的js是这个游戏的VIP玩家,他拥有两项特权操作:
1、让平面内的所有怪物向任意一个相同的方向移动相同的距离d。
2、让平面内的所有怪物以js为中心旋转相同的角度θ。

js在进行射击前,可以无限次的使用这两项特权操作。js想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮伟大的js吧。

Input
输入包括三行。

第一行中有一个正整数n(1 <= n <= 100),表示平面内的怪物数量。

第二行包括n个由空格分隔的整数x[i](-1,000,000 <= x[i] <= 1,000,000),表示每只怪物的横坐标。

第二行包括n个由空格分隔的整数y[i](-1,000,000 <= y[i] <= 1,000,000),表示每只怪物的纵坐标。

Output
输出js一次性最多能消灭的怪物数。

Sample Input
5
0 -1 1 1 -1
0 -1 -1 1 1
Sample Output
5

枚举两个点,连成一条线。每次检查在线上有多少点,不在线上的点往线上作投影,当线上的点+某个投影的坐标的所有点>答案的时候,更新答案。

是否三点一线用向量是否平行,投影也用向量坐标运算。

技巧:投影用map来存储,遍历的时候用map的迭代器进行遍历。重载运算符实现坐标相减得到向量的功能。

答案初始化为1;因为如果没有能构成线点,那么将不运算

#include<bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
struct point{
	ll x, y;
	point(){}
	point(ll x,ll y):x(x),y(y){}
	point operator -(point tp)
	{
		return point(x-tp.x,y-tp.y);
	}
}p[110];
ll dot(point a,point b)
{
	
Read the rest

【生成函数】果苣拼盘

Description
果苣是一类高贵的水果的统称。

而果苣拼盘则是使用这些高贵的水果制成的拼盘。制作一份果苣拼盘,需要满足如下限制:
     1. 必须使用特定的n种果苣。
     2. 第i种果苣的数量不能少于li 份,也不能多于ri 份
     3. 果苣的总份数要恰好为m份

果苣想知道,一共有多少种不同的果苣拼盘的制作方案?

Input
多组数据

第一行有一个整数T(T<=20),代表数据组数。

对每组数据,第一行有两个由空格分隔的整数n和m(1<=n<=20, 1<=m<=100),表示果苣的种类和拼盘需要的果苣总份数。

接下来n行,每行有两个由空格分隔的整数li 和ri (0<= li <= ri <= 10),描述第i种果苣数量的限制。

Output
对每组数据,输出满足限制条件的方案数。

Sample Input
2
2 3
1 2
1 2
3 5
0 3
0 3
0 3
Sample Output
2
12
HINT
对于两种方案,当有任意一种水果的份数不同时,则两种方案不同。

每种水果无论取几个都只有一种取法。生成函数,最后的系数就是答案,即多项式的乘法。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll a[220][1100]={0};
ll t,n,m,l[220],r[220];
ll ans[1100],tmp[1100];
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		memset(ans,0,sizeof(ans));
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld%lld",&l[i],&r[i]);
			m-=l[i];
			
Read the rest

【欧拉函数||容斥】gcd之和

Description
给出一个数列,求数列中任意一对数的最大公因数之和。
最大公因数的定义可以查看 baike.baidu.com/item/最大公因数 

Input
 多组数据。
输入的第一行包括一个整数表示数据组数T(1<=T<=10)。
每组数据的第一行包括一个整数表示数列的长度N(1<=N<=10000)。
第二行包括N个整数,第i个整数表示数列的第i个数ai(1<=ai<=10000)。

Output
每组数据在单独的一行中输出数列中任意一对数的最大公因数之和。 

Sample Input
3
3
2 1 3
4
4 3 9 6
7
7 7 7 7 7 7 7
Sample Output
3
13
147
HINT
 对于第一组数据:


gcd(2,1)+gcd(2,3)+gcd(1,3)=1+1+1=3

对于第二组数据:

gcd(4,3)+gcd(4,9)+gcd(4,6)+gcd(3,9)+gcd(3,6)+gcd(9,6)=1+1+2+3+3+3=13

对于第三组数据:

gcd(7,7)*(6+5+4+3+2+1)=7*21=147 

关于这题有很多种解法。

1.容斥

假设d为N公因数,那么公因数之和就是所有的d乘上,其中num(d)指的是d出现的次数。因为任意两个数才有公约数,从有d这个公因数的所有数中选择两个即可。

然而这下算出来的是所有公因数的和,我们需要的是最大公因数的和。所以要除重,可以利用容斥原理。d算出的答案减去d的倍数算出的答案即为最大公约数之和。例如最大公因数为2的,就可以算出公因数为2的,再减去公因数和为4,8,16…的。倒过来容斥就可以了。

代码见 题解 F

2.欧拉函数

首先欧拉函数有个性质:也就是说n的所有因数的欧拉函数之和等于n本身。

假设,则x,y小于n的公约数一定是相同的。可以得到:任意两数的gcd等于他们的公因数的欧拉函数值之和。则同样有某个gcd的和为

其中可以看作是0..num(n)-1的等差求和公式: 。n则可以写为

$$

可以看出每个公因数的Φ值乘上自己出现的次数都会对gcd的和做出一定贡献。而且因为每个d都有对应的gcd,所以不存在重复的情况。

那每加入一个数x。可以把答案加上

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+233;
ll phi[maxn+23]={0};
ll a[maxn+23];
vector<ll> d[maxn+23];
void phi_t()
{
	for(ll i=2;i<=maxn;i++) 
Read the rest

【矩阵快速幂-构造】I – Algebraic Problem LightOJ – 1070

Given the value of a+b and ab you will have to find the value of an+bn. a and b not necessarily have to be real numbers.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be 
Read the rest

【组合数求模】K – Combinations LightOJ – 1067

Given n different objects, you want to take k of them. How many ways to can do it?

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.

Take 1, 2

Take 1, 3

Take 1, 4

Take 2, 3

Take 2, 4

Take 3, 4

Input
Input starts with an integer T (≤ 2000), denoting the number of test cases.

Each test case contains two integers n (1 
Read the rest

【组合数学】J – Rooks LightOJ – 1005

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move vertically or horizontally from its current position and two rooks attack each other if one is on the path of the other. In the following figure, the dark squares represent the reachable locations for rook R1 from its current position. The figure also shows that the rook R1 and R2 are in attacking positions where 
Read the rest