这两天掉分有点严重，不知不觉的，心态也慢慢地发生了一些难以言说的变化
D题：
题意：
有一个n行m列的八数码棋盘，上面每个棋子都编号为1~n*m-1，每次取第1，p，p+1，2（p+1）... n（p+1）个棋子，将他们依次排成新的一列，问存不存在情况能将初始情况转换到最终状态
解法：
对于八数码问题，能从a状态转换到b状态的条件是a状态的逆序对个数的奇偶性和b状态的奇偶性一样，这道题判断逆序对个数有点trick，并不能拿树状数组求，会T，只能观察找规律，发现选取每个数对逆序对个数的贡献为一个首项为0，公差为（p-1）的等差数列，依次处理即可，复杂度为O（2*N）
1 #include<cstdio> 2 #include<set> 3 using namespace std; 4 typedef set<int>::iterator si; 5 set<int>s; 6 int f[1000 * 1000 + 5]; 7 int vis[1000 * 1000 + 5]; 8 9 int main() { 10 int T; scanf("%d", &T); 11 while (T--) { 12 s.clear(); 13 int n, m, p; scanf("%d%d%d", &n, &m, &p); 14 int num = n*m - 1; 15 int ans = 0; 16 while (num > p) { 17 int nn = (num - 1) / p + 1; 18 ans += 0 + nn*(nn - 1)*(p - 1) / 2; 19 num -= nn; 20 } 21 if (ans & 1)printf("NO "); 22 else printf("YES "); 23 } 24 return 0; 25 }
K题：
题意：
有n个点的坐标，这些坐标都是整数，问这些点能够组成多少个多边形
解法：
由于点的坐标都为整数，所以只有四边形满足，这样我门只需要枚举有多少个正方行即可
方法是每次任意选取两个点，然后算出来他上下方的两个点，判断这两个点是否给出即可
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn = 500 + 5; 6 struct point { int x, y; }; 7 int a[maxn][maxn]; 8 point p[maxn]; 9 10 int check(int x1,int y1,int x2,int y2) { 11 if (x1 > 0 && x1 < maxn&&y1>0 && y1 < maxn&&x2>0 && x2<maxn&& y2>0&&y2 < maxn) { 12 if (a[x1][y1] && a[x2][y2])return 1; 13 else return 0; 14 } 15 return 0; 16 } 17 18 int main() { 19 int n; 20 while (scanf("%d", &n) != EOF) { 21 memset(a, 0, sizeof(a)); 22 for (int i = 0; i < n; i++) { 23 int x, y; scanf("%d%d", &x, &y); 24 x += 101, y += 101; 25 p[i].x = x; p[i].y = y; 26 a[x][y] = 1; 27 } 28 int ans = 0; 29 for (int i = 0; i < n; i++) { 30 for (int j = i + 1; j < n; j++) { 31 int x1 = p[j].x - p[j].y + p[i].y; 32 int y1 = p[j].y + p[j].x - p[i].x; 33 int x2 = p[j].x - p[j].y + p[i].y - p[j].x + p[i].x; 34 int y2 = p[j].y + p[j].x - p[i].x - p[j].y + p[i].y; 35 if (check(p[i].x, p[i].y, p[j].x, p[j].y) && check(x1, y1, x2, y2)) 36 ans += 1; 37 x1 = p[j].x + p[j].y - p[i].y; 38 y1 = p[j].y - p[j].x + p[i].x; 39 x2 = p[j].x + p[j].y - p[i].y - p[j].x + p[i].x; 40 y2 = p[j].y - p[j].x + p[i].x - p[j].y + p[i].y; 41 if (check(p[i].x, p[i].y, p[j].x, p[j].y) && check(x1, y1, x2, y2)) 42 ans += 1; 43 } 44 } 45 printf("%d ", ans / 4); 46 } 47 return 0; 48 }
题意：求第ab个斐波那契数除以n的余数，0<=a,b<264 , 1<= n <=1000
解法：见代码
1 /* 2 求第a^b项的斐波那契数 3 注意斐波那契数列在mod n的情况下会出现循环，循环节最长为n*n 4 由此求出循环节长度即可 5 1. 注意a或者b的范围是2^64，所以要用到 unsigned long long 6 2. 注意对a^b%n的正确姿势是pow_mod(a%n, b, n)。 7 而不是pow_mod(a, b, t[n])。这个很容易写错！ 8 */ 9 10 #include<cstdio> 11 #include<iostream> 12 using namespace std; 13 typedef unsigned long long ull; 14 const int maxn = 1000 + 5; 15 int f[maxn*maxn+100]; 16 17 int poww(ull a, ull p, int Mod) 18 { 19 int ret = 1; 20 while (p) 21 { 22 if (p & 1)ret *= a, ret %= Mod; 23 a *= a; a %= Mod; 24 p >>= 1; 25 } 26 return ret; 27 } 28 29 int main() { 30 int T; scanf("%d", &T); 31 while (T--) { 32 ull a, b, n; cin >> a >> b >> n; 33 if (n == 1 || !a) { printf("0 "); continue; } 34 f[0] = 0, f[1] = 1, f[2] = 1; 35 int cnt; 36 for (int i = 3; i <= n*n+5; i++) { 37 f[i] = (f[i - 1]%n + f[i - 2]%n) % n; 38 if (f[i] == 1 && f[i - 1] == 1) { 39 cnt = i - 2; break; 40 } 41 } 42 ull pos = poww(a%cnt, b, cnt); 43 printf("%d ", f[pos]); 44 } 45 return 0; 46 }
Uva12169（扩展欧几里得）
题意：
已知xi=(a*xi-1+b) mod 10001，且告诉你x1,x3.........x2*t-1,让你求出其偶数列
解法：
令 x2 = ( ax1 + b ) mod 10001，x3 = ( ax2 + b ) mod 10001
解得：x3+10001k=a2x1+( a + 1) b
移像得：x3 - a2x1=( a + 1) b - 10001k
把 b 和（-k）看成是未知数，这就是求解一个ax+by=c的方程，扩展欧几里得可解
见代码
/* 由于a的范围只有1e5，所以我们可以直接枚举a的所有值， 然后根据公式求出b的值，之后根据a和b的值递推所有的原数列的值 期间会用到扩展欧几里得解线性方程组 如果有不一样的，说明就不存在，重来 */ #include<cstdio> using namespace std; typedef long long ll; const int mod = 10001; ll f[2*10000], n; //扩展欧几里得解线性方程组 ll exgcd(ll a, ll b, ll &x, ll &y){ if (b == 0){ x = 1, y = 0; return a; } ll r = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b*y; return r; } inline bool linear_equation(ll a, ll b, ll c, ll &x, ll &y){ ll d = exgcd(a, b, x, y); if (c%d) return false; ll k = c / d; x *= k; y *= k; //求得的只是其中一组解 return true; } bool check(ll a,ll b) { for (int i = 2; i <= n * 2; i++) { ll now = (a*f[i - 1] + b) % mod; if (i & 1) { if (now == f[i]) continue; else return false; } else f[i] = now; } return true; } int main() { scanf("%d", &n); for (int i = 1; i <= n * 2; i += 2) scanf("%lld", &f[i]); for (ll a = 0; a <= 10001; a++) { ll b, k; if (!linear_equation(a + 1, mod, f[3] - a*a*f[1], b, k))continue; if (check(a, b)) break; } for (int i = 2; i <= 2 * n; i+=2) { printf("%lld ", f[i]); } return 0; }
题意：
输入整数n，要求至少两个正整数，使得他们的最小公倍数为n，且这些整数的和最小
解法：
首先假设我们知道了一系列数字a1，a2，a3……an，他们的LCM是n，那么什么时候他们是最优解呢，当他们两两互质的时候
为了方便我们以两个数来说明问题。
a和b的LCM是n，GCD是m，那么n=a/m*b ， 它们的和就是sum=a+b;
如果m不为1（即a和b不互质），那么我们为什么不优化一下，将a变为a=a/m呢？，改变后a和b的LCM依然是n，但是他们的和显然减少了
所以我们得到最重要的一个性质，要想a1，a2，a3……an的和最小，要保证他们两两互质，只要存在不互质的两个数，就一定可以近一步优化
那我们怎么保证两两互质呢？方法其实很简单，直接分解质因子
例如24=2*2*2*3 ， 只能分解为8和3，因为这里有3个2，这3个2必须在一起，如果分开了这3个2，这出现有两个数会有一个公共的质因子2，并且会使这两个数的LCM不是24
再例如72=2*2*2*3*3，只能分为8和9，因为3个2和2个3都不能分开，他们必须在一次
所以，我们将一个数n分解为质因子后，顺便做一个处理，在除干净一个质因子的同时，将他们乘起来作为一个因子，处理完后会得到多个因子，他们之间同样满足两两互质的性质
然后是进一步的分析
例如264600=8*27*25*49 ， 只是由3个2,3个3,2个5,2个7，处理后得到的因子，那么8,27，25,49的LCM是264600，并且两两互质，他们还要不要处理呢？不需要了，直接将他们加起来就是我们要的答案！为什么呢？可以将8,27,25,49这些数字乘起来，无论怎样乘都好，最后得到的数字它们的LCM依然是n，但是乘起来再相加显然比直接相加要大得多！
所以我们已经得到了这个问题的解法
1.将一个数分解成质因子，将相同的因子乘起来作为一个处理后的因子
2.将处理后得到的多个因子直接相加就是答案
3.因为题目说只要需要两个数字，所以对于1和素数我们需要小心。对于素数，我们只能分解出一个因子就它自己，对于1一个因子都分解不出来（我们不把1当做因子），他们的答案都是n+1，因为只有1和n的LCM是n
1 /* 2 唯一分解定理的应用，work_quality_factor就是分解质因数的板子 3 将一个数分解质因数，将他们所有相同的因子乘起来作为一个新的因子，最后的和就是这些因子和 4 */ 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 typedef long long ll; 9 const int maxn = 100; 10 ll fac[maxn], frq[maxn]; 11 12 ll poww(ll a, ll b) { 13 ll ans = 1, base = a; 14 while (b != 0) { 15 if (b & 1 != 0) 16 ans *= base; 17 base *= base; 18 b >>= 1; 19 } 20 return ans; 21 } 22 23 ll work_quality_factor(ll n, ll quality_fac[], ll frequency[]) 24 {//n是待分解的数,quality_fac[]会存放它包含的质因子,而frequency[]存放对应次数 25 //如q_f[k]=7,fre[k]=2就表示质因数分解后里面包含有7,且次数是2 26 //函数返回有几种质因子,比如分解了25就返回1,分解28返回2 27 ll res, temp, i; 28 res = 0; 29 temp = n; 30 for (i = 2; i*i <= temp; i++) 31 if (temp%i == 0) 32 { 33 quality_fac[res] = i; 34 frequency[res] = 0; 35 while (temp%i == 0) 36 { 37 temp = temp / i; 38 frequency[res]++; 39 } 40 res++; 41 } 42 if (temp > 1) 43 { 44 quality_fac[res] = temp; 45 frequency[res++] = 1; 46 } 47 return res; 48 } 49 50 int main() { 51 ll n; int kase = 1; 52 while (scanf("%lld", &n) && n) { 53 ll num = work_quality_factor(n, fac, frq); 54 ll ans = 0; 55 if (num == 0 || num == 1) ans = n + 1; 56 else { 57 for (int i = 0; i < num; i++) { 58 ans += poww(fac[i], frq[i]); 59 } 60 } 61 printf("Case %d: %lld ", kase++, ans); 62 } 63 return 0; 64 }
题意：
输入整数n，1<= n <=3e7，问有多少个整数对（a，b）满足：1 <= b <= a <= n，且gcd（a，b）== a XOR b
解法：
a^b = c 等价于a^c = b 所以枚举a和c，而a和c全部枚举肯定TLE，所以高效算法：通过c是a的约数这个关系来枚举会减小循环，必须要将c放在循环外面，因为c的情况比较少。其实本题就是要求：c=a-b（规律）,c=a^b
1 /* 2 打表找规律 3 */ 4 #include<cstdio> 5 #include<cmath> 6 #include<cstring> 7 using namespace std; 8 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } 9 const int maxn = 3e7 + 5; 10 int ans[maxn]; 11 12 void generate() { 13 //类似于筛素数，我们的外层是公约数（素数） 14 //注意筛素数的时候我们先筛小的，也就是最基本的那个，这样子就可以筛掉所有最基本的那个的倍数 15 for (int c = 1; c <= maxn / 2; c++) { 16 for (int a = c + c; a <= maxn; a += c) { 17 int b = a - c; 18 if ((a^b) == c) ans[a]++; 19 } 20 } 21 for (int i = 2; i < maxn; i++)ans[i] += ans[i - 1]; 22 } 23 24 int main() { 25 int T; scanf("%d", &T); 26 int kase = 0; 27 generate(); 28 while (T--) { 29 int n; scanf("%lld", &n); 30 printf("Case %d: %d ", ++kase, ans[n]); 31 } 32 return 0; 33 }