【数论】三角关系

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

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

VScode配置g++编写c++

  1. 将g++添加到环境遍历
  2. 安装插件”code runner”
  3. 设置-插件-run code configuration-Run in terminal 勾选上(否则如果程序里有输入等待将无法继续)
  4. 下载微软官方插件C/C++ 以便于调试
  5. 在目录下的.vs文件夹里面生成:launch.json/tasks.json
{
    // 使用 IntelliSense 了解相关属性。 
    // 悬停以查看现有属性的描述。
    // 欲了解更多信息,请访问: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(gdb) Launch",
            "type": "cppdbg",
            "request": "launch",
            
            
            "program": "${fileDirname}/${fileBasenameNoExtension}.exe",
            
            
            //"program": "enter program name, for example ${workspaceFolder}/a.exe",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": true,
            "MIMode": "gdb",
            //"miDebuggerPath": "/path/to/gdb",
            "miDebuggerPath": "C:/Program Files (x86)/Dev-Cpp/MinGW64/bin/gdb.exe",
            "preLaunchTask": "g++",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ]
        }
    ]
}
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

【矩阵快速幂】hyper Fibonacci 数列

Description
令F(i)表示斐波那契数列的第i项。
S1(i)表示F数列的前i项和。
S2(i)表示S1数列的前i项和。
S3(i)表示S2数列的前i项和。
S4(i)表示S3数列的前i项和。
S5(i)表示S4数列的前i项和。
S6(i)表示S5数列的前i项和。
S7(i)表示S6数列的前i项和。
S8(i)表示S7数列的前i项和。
求S8(N)。答案可能很大,请对1000000007取模。
斐波那契数列的定义可以查看https://baike.baidu.com/item/斐波那契数列

Input
多组数据。
输入的第一行包括一个整数表示数据组数T(1<=T<=1000)。
每组数据的第一行包括一个整数表示题目所说的N(1<=N<=1000000000000000000)。

Output
每组数据在单独的一行中输出S8(N)。


Sample Input
4
1
2
3
4
Sample Output
1
9
46
175
HINT
F数列前四项:1 1 2 3

S1数列前四项:1 2 4 7

S2数列前四项:1 3 7 14

S3数列前四项:1 4 11 25

S4数列前四项:1 5 16 41

S5数列前四项:1 6 22 63

S6数列前四项:1 7 29 92

S7数列前四项:1 8 37 129

S8数列前四项:1 9 46 175 

由题目给的hint其实已经看出来了

其他项也是如此

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p=1000000007;
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