2012年9月23日
修改自：
http://hi.baidu.com/arorua_/item/381bb88d817b122d100ef3a1Number one：poj2480
http://poj.org/problem?id=2480题意是：求
∑gcd(i, N) 1<=i <=N. N(1 < N < 2^31)
解法：
∑gcd(i, n) ==
∑(fac[i] * phi(n / fac[i])) (fac存的是n的所有约数)
代码：
poj2480
//sigma(gcd(i, n)) == sigma(fac[i] * phi(n / fac[i]))
#include <cstdio>
#include <cstring>
using namespace std;
long long n, ans;
int fac[32000], cnt;
//get eular
long long get_eular(long long n) {
long long res = 1;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
n /= i; res = res * (i - 1);
while (n % i == 0) {
n /= i; res = res * i;
}
}
}
if (n > 1) res *= n - 1;
return res;
}
void get_factor(long long n) {
cnt = 0;
memset(fac, 0, sizeof(fac));
for (int i = 1; (long long)i * i <= n; i++) {
if (n % i == 0) {
if (i * i == n) {
fac[cnt++] = i; return ;
}
fac[cnt++] = i;
fac[cnt++] = n / i;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("p2480", "r", stdin);
#endif
while (scanf("%lld", &n) != EOF) {
ans = 0;
get_factor(n);
for (int i = 0; i < cnt; i++)
ans += fac[i] * (get_eular(n / fac[i]));
printf("%lld\n", ans);
}
return 0;
}
2012年9月18日
2012年9月17日
筛素数和欧拉函数
/*******************************************************************************
素数＋欧拉函数表
*******************************************************************************/
const int size = 1000010;
int phi[size], prime[size];
bool check[size];
void excelphi() {
memset(check, false, sizeof(check));
phi[1] = 1;
int tot = 0;
for (int i = 2; i <= size; i++) {
if (!check[i]) {
prime[tot++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < tot; j++) {
if (i * prime[j] > size) break;
check[i*prime[j]] = true;
if (i % prime[j] == 0) {
phi[i*prime[j]] = phi[i]*prime[j];
break;
} else {
phi[i*prime[j]] = phi[i]*(prime[j] - 1);
}
}
}
}
再贴个筛区间素数的：
筛区间素数
/*******************************************************************************
筛区间素数
*******************************************************************************/
const int size = 32000, maxn = 1000010;
int check[maxn], prime[size], ans[maxn], cnt;
void get_small_prime() {
cnt = 0;
memset(check, 0, sizeof(check));
for (int i = 2; i < size; i++) {
if (!check[i]) prime[cnt++] = i;
for (int j = i * i; j < size; j += i)
check[i] = 1;
}
}
void get_large_prime(int l, int r) {
cnt = 0;
memset(ans, 0, sizeof(ans));
memset(check, 0, sizeof(check));
for (int i = 0; prime[i] * prime[i] <= r; i++)
for (int j = l / prime[i]; j * prime[i] <= r; j++)
if (j > 1 && j * prime[i] >= l)
check[j * prime[i] - l] = 1;
for (int i = l; i <= r; i++)
if (!check[i-l] && i > 1)
ans[cnt++] = i;
}
2012年8月9日
学习状态压缩，首先要会基础的
位运算，然后要知道位运算的一些基本应用，这方面
Matrix67大牛总结的很好。学习了这些，接下来可以看看
这篇论文，讲的挺好。
2012年8月4日
贴个专题
http://acm.hdu.edu.cn/forum/read.php?tid=15908FOJ1683：
http://acm.fzu.edu.cn/problem.php?pid=1683题意：已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。
题解：找到递推矩阵
[S(n-1)] [1 3 2 7] [S(n)]
[F(n-1)] * [0 3 2 7] = [F(n)]
[F(n-2)] [0 1 0 0] [F(n-1)]
[F(n-3)] [0 0 1 0] [F(n-2)]
然后矩阵快速幂就破了 代码就不贴了。
HDU2256：http://acm.hdu.edu.cn/showproblem.php?pid=2256
这题可以用矩阵乘法解，非常巧妙。。。
贴个解题报告吧：
http://chensmiles.blog.163.com/blog/static/12146399120107310
4757471/
今天做了一下背包专题，连接
http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=10736#overview密码是：sduacm 个人觉得这几题都很不错
额，第一题就不说了，普通的0－1背包
G题(HDU4091)是2011年上海区预赛第一题，据说AC这道题就可以拿铜牌了(囧) 题意是给俩个物品，每个物品有价值和体积，显然直接贪心不对，可以当作背包来解，但背包的容量很大，不能直接背包。这题的做法是：现求总容量对俩个物品的体积的LCM取余的余数，然后在余数中枚举，对其他的容量贪心，很容易证明这个思路的正确性。
HDU4091
//枚举即可破 因为只有俩种物品 找到俩种物品体积的lcm然后去余 对余数枚举
//然后对其他的贪心
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int t;
LL n, s1, v1, s2, v2;
while (scanf("%d", &t) != EOF) {
for (int cas = 1; cas <= t; cas++) {
scanf("%I64d%I64d%I64d%I64d%I64d", &n, &s1, &v1, &s2, &v2);
LL tmp = 2 * s1 * s2 / gcd(s1, s2);
LL tem = n / tmp;
n %= tmp;
if (tem) {
tem--; n += tmp;
}
LL res = max((tem)*(tmp/s1)*v1, (tem)*(tmp/s2)*v2);
LL temp = 0;
if (s2 > s1) {
swap(s1, s2);
swap(v1, v2);
}
for (int i = 0; i <= n / s1; i++)
if (temp < i*v1 + (n-i*s1)/s2*v2)
temp = i*v1 + (n-i*s1)/s2*v2;
res += temp;
printf("Case #%d: %I64d\n", cas, res);
}
}
return 0;
}
I题(SGU259)单机调度问题，题意是只有一个打印机，有许多传单需要打印和分发，打印的时间T[i]，分发的时间是L[i]，每个传单必须先打印后分发，假设有很多分发员，问将左右的传单打印并且分发完所用完的最短时间。这题直观有个感觉就是因为分发员有很多人，分发时间长的传单显然先打印比较好，并且很容易证明这个贪心思想的正确性。因此对L从大到小排序，然后再求的时间就是最短的时间。
SGU259
/*
* Author: whxnwjq
* Algorithm:
* File Name: I.cpp
*/
#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <stack>
#include <set>
using namespace std;
#define PI acos(-1)
#define LL long long
const int inf = 0x7fffffff;
const double eps = 1e-6;
struct Node {
int t, l;
}a[222];
bool cmp(Node x, Node y) {
return x.l > y.l;
}
int main() {
int T, sum, tmp;
while (cin >> T) {
sum = 0, tmp = 0;
for (int i = 0; i < T; i++)
cin >> a[i].t;
for (int i = 0; i < T; i++)
cin >> a[i].l;
sort(a, a+T, cmp);
for (int i = 0; i < T; i++) {
sum += a[i].t; tmp -= a[i].t;
if (tmp < 0) tmp = 0;
tmp = max(a[i].l, tmp);
}
sum += tmp;
cout << sum << endl;
}
return 0;
}
SPOJ39_PIGBANK：这题是个经典的完全背包问题，题意是有个储蓄罐，知道了空的时候的质量和装满硬币的质量，给了一些硬币的质量和价值，求储蓄罐装满时硬币的最小价值。
经典题。
SPOJ39_PIGBANK
/*
* Author: phonism
* Algorithm: 完全背包经典题
* File Name: spoj39_PIGBANK.cpp
*/
#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <stack>
#include <set>
using namespace std;
#define PI acos(-1)
#define LL long long
const int inf = 10101001;
const double eps = 1e-6;
int main() {
int t, n, m, a, u[1000], v[1000], dp[11000];
cin >> t;
while (t--) {
cin >> n >> m >> a;
for (int i = 1; i <= a; i++)
cin >> u[i] >> v[i];
for (int i = 0; i < 11000; i++)
dp[i] = inf;
dp[0] = 0;
for (int i = 1; i <= a; i++)
for (int j = v[i]; j <= m - n; j++)
dp[j] = min(dp[j], dp[j-v[i]] + u[i]);
if (dp[m-n] != inf) {
cout << "The minimum amount of money in the piggy-bank is ";
cout << dp[m-n] << "." << endl;
}
else puts("This is impossible.");
}
return 0;
}
HDU4091
2012年8月3日
今天发现这个网站
http://www.donews.com/挺不错的 虽然上面没有什么的算法，但是都是IT行业一些比较前沿的新闻什么的，对以后应该会有作用吧