313.64位整数乘法
题目:
求a乘b对p取模的值。
输入格式
第一行输入整数a，第二行输入整数b，第三行输入整数p。
输出格式
输出一个整数，表示 a*b mod p 的值。
数据范围
1≤a, b, p≤10¹⁸
输入样例
3
4
5
输出样例
2
思路:
1.直接算会爆long long，这里我们用不需要高精度的方法，也就是龟速乘，思想上类似快速幂。
代码(c++):
#include <cstdio>
typedef long long LL;
LL qadd(LL a, LL b, LL p)
{
LL res = 0;
while (b)
{
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
int main()
{
LL a, b, p;
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld\n", qadd(a, b, p));
return 0;
}
314.费解的开关
题目:
你玩过“拉灯”游戏吗？
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。
数据范围
0<n≤500
输入样例
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例
3
2
-1
思路:
1.本题有关递推。我们可以用bfs来做，从终止状态倒推6步，也就是按6次开关，能到达的状态就是合法状态。但是这样时间复杂度不太保险。所以我们用递推，每个灯最多按一次，因为按两次是没有任何意义的。其次按的顺序是无所谓的，所以我们从上往下来递推，推出每个开关应不应该去按下。我们举个例子
10111
01101
10111
10000
11011
假设第一行的开关已经被锁死，那么我们看第一行第一个元素，因为它已经是1了，而且目前能影响它的只有第二行第一个元素。所以我们可以知道第二行第一个元素是绝对不可以按的。第一行第二个元素是0，所以代表第二行第二个开关必须按一下。所以我们可以发现，一旦第一行的状态锁死了，那么我们可以通过第一行的状态去推出第二行开关的状态，以此类推，可以推出所有状态。如果最后一行有0，那么状态不合法，如果最后一行没0，那么合法。所以我们只需要枚举第一行所有操作方按即可，对于每种操作方案，我们把每种状态推出来，并且判断是否合法即可。
2.另外，实际上本题最快的做法是高斯消元。但是此处不采用。
代码(c++):
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 6; //字符串最后有'\0'字符，所以要多开一个
char g[N][N], bg[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};
void turn(int x, int y) //按一下第x行第y列的开关
{
for (int i = 0; i < 5; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
g[a][b] ^= 1;
}
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
for (int i = 0; i < 5; i ++ ) scanf("%s", bg[i]);
int res = 10; //比六大就可以
for (int op = 0; op < 32; op ++ ) //2⁵，枚举第一行的情况
{
int cnt = 0;
memcpy(g, bg, sizeof g);
for (int i = 0; i < 5; i ++ ) //枚举第一行
if (op >> i & 1) //如果当前位是1
{
turn(0, i);
cnt ++ ;
}
for (int i = 0; i < 4; i ++ ) //递推出第1~4行开关的状态
for (int j = 0; j < 5; j ++ )
if (g[i][j] == '0')
{
turn(i + 1, j); //按0下面的开关
cnt ++ ;
}
bool success = true;
for (int i = 0; i < 5; i ++ ) //// 检查最后一行灯是否全亮
if (g[4][i] == '0')
success = false;
if (success && res > cnt) res = cnt;
}
if (res > 6) res = -1;
printf("%d\n", res);
}
return 0;
}
315.约数之和
题目:
假设现在有两个自然数A和B，S是Aᴮ的所有约数之和。
请你求出S mod 9901的值是多少。
输入格式
在一行中输入用空格隔开的两个整数A和B。
输出格式
输出一个整数，代表S mod 9901的值。
数据范围
0≤A, B≤5×10⁷
输入样例
2 3
输出样例：
15
思路:
1.如果一个数为N能够表示成N＝p₁ᵃ¹×……×pₖᵃᵏ，那么约数之和为(1+p₁+p₁²+……+p₁ᵃ¹)×……×(1+pₖ+pₖᵃᵏ)。对于Aᴮ，我们先对A分解质因数。那么Aᴮ＝p₁ᵃ¹ᴮ×……×pₖᵃᵏᴮ，直接用公式求即可。可是直接用公式，每个括号里会有aₖB+1项，我们知道0≤A, B≤5×10⁷，非常之大。所以我们此处可以采用等比数列求和公式。即p⁰+……+pᵏ⁻¹＝(pᵏ-1)/(p-1)。
2.此处我们采用递归的思想。对于p⁰+……+pᵏ⁻¹
代码(c++):
#include <cstdio>
const int mod = 9901;
int qmi(int a, int k)
{
int res = 1;
a %= mod;
while (k)
{
if (k & 1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
int sum(int p, int k)
{
if (k == 1) return 1; //p⁰
if (k % 2 == 0) return (1 + qmi(p, k / 2)) * sum(p, k / 2) % mod; //k为偶数
return (sum(p, k - 1) + qmi(p, k - 1)) % mod; //k为奇数
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
int res = 1;
for (int i = 2; i * i <= a; i ++ ) //对A分解质因数
if (a % i == 0)
{
int s = 0;
while (a % i == 0)
{
a /= i, s ++ ;
}
res = res * sum(i, b * s + 1) % mod;
}
if (a > 1) res = res * sum(a, b + 1) % mod;
if (a == 0) res = 0;
printf("%d\n", res);
return 0;
}
316.分形之城
题目:
城市的规划在城市建设中是个大问题。
不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。
而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：
当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。
对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。
虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 N，编号为 A 和 B 的两个街区的直线距离是多少。
街区的距离指的是街区的中心点之间的距离，每个街区都是边长为 10 米的正方形。
输入格式
第一行输入正整数 n，表示测试数据的数目。
以下 n 行，输入 n 组测试数据，每组一行。
每组数据包括三个整数 N,A,B，表示城市等级以及两个街区的编号，整数之间用空格隔开。
输出格式
一共输出 n 行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。
数据范围
1≤N≤31
1≤A,B≤2²ᴺ
1≤n≤1000
输入样例
3
1 1 2
2 16 1
3 4 33
输出样例
10
30
50
思路:
1.我们首先应该解决一个问题，就是给了我们编号，我们怎么去求坐标？坐标有了就可以直接求距离。我们以左上角为原点竖直方向为x轴，水平方向为y轴。首先我们把它分为四部分，如图所示
那么我们先根据编号去判断这个点在哪个部分。n级城市的每个小部分的边长为2ⁿ⁻¹，那么每个部分就是2²ⁿ⁻²个街区，设block为2²ⁿ⁻²。那么用A/block就可以得到A在哪个部分。
于是进一步的，我们进行递归。我们首先要明确，假设现在是N级城市，当我们进入N-1级的城市时候，我们需要减去一个偏移量。如上图，假设我们现在进入②部分，那么我们的偏移量就是4，也就是mod 4，于是(x, y)＝get(N-1, A%block)。所以就能求出在N-1级城市里的坐标。
再通过下图变换，即可求出N-1级城市在N级城市的坐标。经历一个N级编号→……→1级编号→1级坐标→……→N级坐标的过程。
其中0为左上角部分，1为右上角部分，2为右下角部分，3为左下角部分。
代码(c++):
#include <cstdio>
#include <cstring>
#include <cmath>
typedef long long LL;
struct Point //点坐标
{
LL x, y;
};
Point get(LL n, LL a)
{
if (n == 0) return {0, 0};
LL block = 1ll << n * 2 - 2, len = 1ll << n - 1;
auto p = get(n - 1, a % block); //a % block为子问题编号
LL x = p.x, y = p.y;
int z = a / block; //在哪个部分
if (z == 0) return {y, x};
else if (z == 1) return {x, y + len};
else if (z == 2) return {x + len, y + len};
return {len * 2 - 1 - y, len - 1 - x};
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
LL n, a, b;
scanf("%lld%lld%lld", &n, &a, &b);
auto pa = get(n, a - 1);
auto pb = get(n, b - 1);
double dx = pa.x - pb.x, dy = pa.y - pb.y;
printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 10); //.0lf就是四舍五入
}
return 0;
}
