D - Four-Tower Towers of Hanoi
假设在4个柱子上挪n个个盘子的最小步骤是F[n]，在三个柱子上挪n个盘子的最小步骤是T[n]，则四柱汉诺塔问题，可以分成两部分考虑：
1.先把上面k个盘子用F[k]步挪到B盘；
2.把下面n-k个盘子用T[n-k]步挪到D盘；
3.把B盘上的k个盘子再用F[k]步挪到D盘。
所以可以得到递推式 F[n] = min{ 2 * F[k] + T[n-k] }。
T[n]的公式已经推出：2^n - 1。
题目还有一个要注意的地方：虽然题目保证最后答案不会超过int64的范围，但是计算过程却可能会。
//code source from sk
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1005;
const unsigned __int64 INF = ((__int64)0 - 1);
unsigned __int64 dp[maxn];
unsigned __int64 two[maxn];
void init()
{
two[0] = 1;
for(int i = 1; i < maxn; i++)
two[i] = two[i-1]*2;
dp[0] = 0;
dp[1] = 1;
dp[2] = 3;
dp[3] = 5;
dp[4] = 9;
dp[5] = 13;
for(int i = 6; i < maxn; i++)
{
unsigned __int64 p = INF;
for(int k = i-1; k < i && i-k < 62; k--)
p = min(p, dp[k]*2+two[i-k]-1);
dp[i] = p;
}
// for(int i = 1; i < maxn; i++)
// cout << "dp[" << i << "]:" << dp[i] << endl;
}
int main()
{
init();
int n;
int kase = 1;
while(scanf("%d", &n)!=EOF)
{
printf("Case %d: %I64d\n", kase++, dp[n]);
}
return 0;
}
E - Light Switches
大素数判定 + dfs所有约数
代码许多地方参考了小伙伴的源码还有shoutmon学长的模板。
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
using namespace std;
#define LL __int64
#define INF 99999999999999LL
#define Rand_time 5
#define C 16381
bool cmp(LL a, LL b)
{
return a < b;
}
LL MIN;
LL gcd(LL a, LL b)
{
return a % b ? gcd(b, a % b) : b;
}
//(a * b) % n
LL Multi_mod(LL a, LL b, LL n)
{
LL s = 0;
while(b)
{
if(b & 1) s = (s + a) % n;
a = (a + a) % n;
b >>= 1;
}
return s;
}
//(a ^ b) % n
LL Pow_mod(LL a, LL b, LL n)
{
LL s = 1;
while(b)
{
if(b & 1) s = Multi_mod(s, a, n);
a = Multi_mod(a, a, n);
b >>= 1;
}
return s;
}
//默认1为合数
bool Miller_Rabin(LL n)
{
LL u = n - 1, pre, x;
if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true;
if(n == 1 || !(n % 2) || !(n % 3) || !(n % 5) || !(n % 7) || !(n % 11)) return false;
//把 n-1 分解成 k 个 2 和 奇数 v 的乘积
//则可以把计算 a ^ (n-1) % n，分解成计算 k 次 (a^2) 迭代计算和 a^v % n 的计算
int k = 0;
while(!(u & 1)) u >>= 1, k++;
srand((LL)time(NULL));
for(int i = 0; i < Rand_time; i++)
{
x = rand() % (n - 2) + 2;
x = Pow_mod(x, u, n);
pre = x; //保留x,既x^2 mod n =1 的根
for(int j = 0; j < k; j++)
{
x = Multi_mod(x, x, n);
//如果n是素数那么 x^2mod n = 1，仅有两个根（不同余），+1和-1（n-1）
if(x == 1 && pre != 1 && pre != (n - 1))
return false;
pre = x;
}
if(x != 1) return false;
}
return true;
}
//在O(sqrt(p))的时间复杂度内找到n的一个小因子p
LL Pollard_rho(LL n, int c)
{
LL x, y, d;
int i = 1, j = 2;
srand((LL)time(NULL));
x = rand() % (n - 1) + 1;
y = x;
while(1)
{
i++;
x = (Multi_mod(x, x, n) + c) % n;
d = gcd(y - x + n, n);
if(d != 1 && d != n) return d;
if(x == y) return n;
if(i == j)
{
y = x;
j <<= 1;
}
}
}
//求所有素因子
LL fac[100];
int cnt[100], k, ck;
void find_factor(LL n, int c)
{
LL r, d;
if(n <= 1) return ;
if(Miller_Rabin(n))
{
fac[k++] = n;
return ;
}
r = Pollard_rho(n, c--);
d = n / r;
find_factor(d, c);
find_factor(r, c);
}
LL n, t, b;
void deal()
{
k = ck = 0;
find_factor(b, C);
sort(fac, fac + k, cmp);
cnt[0] = 1;
for(int i = 1; i < k; i++)
{
if(fac[i] == fac[ck]) cnt[ck]++;
else { fac[++ck] = fac[i]; cnt[ck] = 1; }
}
ck++;
}
LL yinzi[12345];
int num;
void dfs(LL val, int k)
{
if(k == ck) { yinzi[num++] = val; return ;}
for(int i = 0, v = 1; i <= cnt[k]; i++)
{
dfs(val * v, k + 1);
v *= fac[k];
}
}
char res[2][4] = {"On", "Off"};
int cas = 0;
void prt(int w)
{
printf("Case %d: %s\n", ++cas, res[w]);
}
int main()
{
// freopen("Light_Switches.in", "r", stdin);
while(~scanf("%I64d%I64d%I64d", &n, &t, &b))
{
t %= n; if(!t) t = n;
if(b == 1LL) { prt(0); continue; }
if(Miller_Rabin(b))
{
if(t >= b) prt(1);
else prt(0);
continue;
}
deal();
num = 0;
dfs(1, 0);
sort(yinzi, yinzi + num, cmp);
// for(int i = 0; i < num; i++) cout << yinzi[i] << ' '; cout << endl;
int id = lower_bound(yinzi, yinzi + num, t) - yinzi;
prt((id + 1) & 1);
}
return 0;
}