一个高中学长问的一道题，挺有意思的。也是简单数论
根据同余的加性，（以下以=代替同余号）
由于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了…………
是Java，把int改为long long就AC了… Read the rest
{
// 使用 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
}
]
}
]
}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;
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()
{
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 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)
{
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];
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;
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++) 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