第一道：Rightmost digit
求N^N次最后一个数字
快速幂mod10咯
代码如下：
#include <cstdio>
#define ll long long
using namespace std;
const int mod = ; int qm(ll a,ll b) {
ll res = ;
while (b) {
if (b & ) res = res * a % mod;
a = a * a % mod; b >>= ;
}
return (int)res;
} int main() {
int T; scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
printf("%d\n", qm((ll)n, (ll)n));
}
return ;
}
好像可以打表找规律。
第二道：又见GCD
从2*b开始枚举c就可以啦
代码如下：
#include <cstdio>
using namespace std; int gcd(int a, int b) {
return b == ? a : gcd(b, a % b);
} int main() {
int n; scanf("%d", &n);
while (n--) {
int a, b;
scanf("%d%d", &a, &b);
for (int i = ; ; i++) {
int c = i * b;
if (gcd(a, c) == b) {
printf("%d\n", c);
break;
}
}
}
return ;
}
第三道：A / B
求 (A / B) % 9973
就是求A * INV(B) % 9973咯
由费马小定理 a^(p-1) ≡ 1(mod p)
所以 a * a^(p-2) ≡ 1(mod p)
所以INV(B) = b ^ (MOD-2)
代码如下：
#include <cstdio>
#define ll long long
using namespace std;
const int mod = ; int qm(ll a,ll b) {
ll res = ;
while (b) {
if (b & ) res = res * a % mod;
a = a * a % mod; b >>= ;
}
return (int)res;
} int main() {
int T; scanf("%d", &T);
while (T--) {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a * qm((ll)b, (ll)mod - ) % mod);
}
return ;
}
第四道：Fibonacci
最基本的矩阵快速幂(今天才学(可见刷题数量之少，以及之菜
和普通快速幂一个道理，就是加上矩阵相乘，以及定义ans变量的时候要定义成单位矩阵的形式
#include <cstdio>
using namespace std;
const int mod = ;
struct Matrix {
int m[][];
} ans, base; Matrix mul(Matrix a, Matrix b) {
Matrix temp;
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
temp.m[i][j] = ;
for (int k = ; k < ; k++) {
temp.m[i][j] = (temp.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
}
}
}
return temp;
} int qm(int n) {
base.m[][] = base.m[][] = base.m[][] = ;
base.m[][] = ;
ans.m[][] = ans.m[][] = ;
ans.m[][] = ans.m[][] = ;
while (n) {
if (n & ) ans = mul(ans, base);
base = mul(base, base);
n >>= ;
}
return ans.m[][];
} int main() {
int n;
while (~scanf("%d", &n) && n != -) {
printf("%d\n", qm(n));
}
return ;
}
扩展欧几里得算法
分为x % k == 0 和 不等于 0 两种情况
如果x % k == 0 直接找一个p + q = k的解打印就好了
如果不整除
令 a = [x / k] 即求 x = a * p + (a + 1) * q 一组整数解
又因为GCD(a, a + 1) = 1 所以就可以先用扩展欧几里得算法求a * p + (a + 1) * q = 1
p q再分别乘以x就好了
#include <cstdio>
#define ll long long
using namespace std; void extgcd(ll a, ll b, ll& d, ll& x, ll& y) {
if (b) {
extgcd(b, a % b, d, y, x);
y -= (a / b) * x;
} else {
d = a;
x = , y = ;
}
} int main() {
int T; scanf("%d", &T);
while (T--) {
ll x, k;
scanf("%lld%lld", &x, &k);
if (x % k == ) {
printf("%d %lld\n", , k);
continue;
}
ll p, q;
ll a = x / k;
ll d;
extgcd(a, a + , d, p, q);
p *= x / d, q *= x / d;
printf("%lld %lld\n", p, q);
}
return ;
}
第六道：zhx's contest
给定一个数n，求先增后减或先减后增或单调增或单调减的排列个数
先看 1，2，...，n
考虑把这个序列变成先增后减的情况 那么就有一个地方得容纳n
从左边n-1个数取0个放到n的右边 C(n-1, 0)
取1个 C(n-1, 1)
取两个 C(n-1, 2) 这两个元素取出来后放到n的右边只有一种排列方式， 就是从大到小排 因为要先增后减 到了n已经停止增 所以只能减
取3个 C(n-1, 3)
......
取n-1个 C(n-1, n-1)
那么可能数就为 C（n-1,0) + C(n-1,1) + ... + C(n-1, n-1) = (1 + 1) ^ (n - 1) = 2 ^ (n - 1)
那么对印的先减后增也是 2 ^ (n - 1)
但是会重复算单调增和单调减的序列
所以答案就是 2^n - 2
n, p <= 1e18
在快速幂的过程中很有可能会溢出long long
所以加上快速乘法(用加法模拟乘法，每一次都取模，这样保证不会溢出)
特判一下1的情况
代码如下：
#include <cstdio>
#define ll long long
using namespace std; ll quick_mul(ll a, ll b, ll mod) {
ll ans = ;
while (b) {
if (b & ) ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= ;
}
return ans;
} ll quick_mod(ll a, ll b, ll mod) {
ll ans = ;
while (b) {
if (b & ) {
ans = quick_mul(ans, a, mod) % mod;
}
a = quick_mul(a, a, mod) % mod;
b >>= ;
}
return ans;
} int main() {
ll n, q;
while (~scanf("%lld%lld", &n, &q)) {
if (n == ) printf("%lld\n", % q);
else
printf("%lld\n", (quick_mod(, n, q) - + q) % q);
}
return ;
}