训练指南第二章-基础问题 P170
 |
2 / 4 | Problem A | UVA 10943 | How do you add? |
|
1 / 2 | Problem B | UVA 10780 | Again Prime? No Time. |
|
1 / 1 | Problem C | UVA 10892 | LCM Cardinality |
|
1 / 4 | Problem D | UVA 11752 | The Super Powers |
|
1 / 3 | Problem E | UVA 11076 | Add Again |
|
1 / 1 | Problem F | UVA 11609 | Teams |
|
1 / 3 | Problem G | POJ 2402 | Palindrome Numbers(LA2889) |
|
1 / 1 | Problem H | UVA 11489 | Integer Game |
|
1 / 6 | Problem I | UVA 10791 | Minimum Sum LCM |
|
1 / 1 | Problem J | UVA 11461 | Square Numbers |
|
1 / 2 | Problem K | UVA 11388 | GCD LCM |
|
1 / 2 | Problem L | UVA 11889 | Benefit |
|
1 / 1 | Problem M | UVA 1319 | Maximum |
|
1 / 1 | Problem N | UVA 1315 | Crazy tea party |
UVA 11388 GCD LCM
显然在合理的情况下，a=G，b=L
#include <bits/stdc++.h>
int main() {
int T;
scanf ("%d", &T);
while (T--) {
int g, l;
scanf ("%d%d", &g, &l);
long long f = 1ll * g * l;
if (l < g || l % g != 0) {
puts ("-1");
} else {
printf ("%d %d\n", g, l);
}
}
return 0;
}
UVA 11889 Benefit
解法一：分解质因数，因为
解法二：数学方法，tb=C/A，当g=GCD(A, tb) != 1，a /= g. tb *= 
#include <bits/stdc++.h>
void get_prime(int n, std::map<int, int> &mp) {
int m = (int) sqrt (n + 0.5);
for (int i=2; i<=m; ++i) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i;
mp[i]++;
}
}
}
if (n != 1) {
mp[n]++;
}
}
int _pow(int x, int n) {
int ret = 1;
while (n) {
if (n & 1) {
ret = ret * x;
}
n >>= 1;
x = x * x;
}
return ret;
}
int solve(int a, int c) {
std::map<int, int> mpa, mpc;
get_prime (a, mpa);
get_prime (c, mpc);
int na = mpa.size (), nc = mpc.size ();
if (na > nc || c % a != 0) {
return -1;
} else {
int ret = 1;
int m = (int) sqrt (c + 0.5);
std::map<int, int>::iterator it;
for (it=mpc.begin (); it!=mpc.end (); ++it) {
if (!mpa.count (it->first) || mpa[it->first] < it->second) {
ret *= _pow (it->first, it->second);
}
}
return ret;
}
}
int main() {
int T;
scanf ("%d", &T);
while (T--) {
int a, c;
scanf ("%d%d", &a, &c);
int ans = solve (a, c);
if (ans != -1) {
printf ("%d\n", ans);
} else {
puts ("NO SOLUTION");
}
}
return 0;
}
#include <bits/stdc++.h>
int GCD(int a, int b) {
return b ? GCD (b, a % b) : a;
}
int solve(int a, int c) {
if (a > c || c % a != 0) {
return -1;
}
int tb = c / a;
int g = GCD (a, tb);
int mul = 1;
while (g != 1) {
mul *= g;
a /= g;
g = GCD (a, tb);
}
return tb * mul;
}
int main() {
int T;
scanf ("%d", &T);
while (T--) {
int a, c;
scanf ("%d%d", &a, &c);
int ans = solve (a, c);
if (ans != -1) {
printf ("%d\n", ans);
} else {
puts ("NO SOLUTION");
}
}
return 0;
}
UVA 10943 How do you add?
这个用隔板法，
#include <bits/stdc++.h>
int binom[205][205];
const int MOD = 1000000;
void init_binom() {
for (int i=1; i<=200; ++i) {
binom[i][0] = binom[i][i] = 1;
for (int j=1; j<i; ++j) {
binom[i][j] = binom[i-1][j-1] + binom[i-1][j];
if (binom[i][j] >= MOD) {
binom[i][j] -= MOD;
}
}
}
}
int main() {
init_binom ();
int n, k;
while (scanf ("%d%d", &n, &k) == 2) {
if (!n && !k) {
break;
}
printf ("%d\n", binom[n+k-1][k-1]);
}
return 0;
}
UVA 10780 Again Prime? No Time.
分解质因数，取n!与m的某个质因数的个数商最小值。n!的某个质因数的个数=
#include <bits/stdc++.h>
int main() {
int T;
scanf ("%d", &T);
for (int cas=1; cas<=T; ++cas) {
int m, n;
scanf ("%d%d", &m, &n);
int ans = 0x3f3f3f3f;
int i = 2;
while (m != 1) {
int cnt = 0;
while (m % i == 0) {
cnt++;
m /= i;
}
if (cnt) {
int nn = n;
int cnt2 = 0;
while (nn) {
cnt2 += nn / i;
nn /= i;
}
ans = std::min (ans, cnt2 / cnt);
}
i++;
}
printf ("Case %d:\n", cas);
if (ans) {
printf ("%d\n", ans);
} else {
puts ("Impossible to divide");
}
}
return 0;
}
UVA 10892 LCM Cardinality
分解质因数，暴力枚举~
#include <bits/stdc++.h>
typedef long long ll;
int GCD(int a, int b) {
return b ? GCD (b, a % b) : a;
}
ll LCM(int a, int b) {
return 1ll * a / GCD (a, b) * b;
}
int main() {
int n;
while (scanf ("%d", &n) == 1) {
if (!n) {
break;
}
std::vector<int> vec;
int m = (int) sqrt (n + 0.5);
for (int i=1; i<=m; ++i) {
if (n % i == 0) {
if (i != n / i) {
vec.push_back (i);
vec.push_back (n / i);
} else {
vec.push_back (i);
}
}
}
int ans = 1; //n n
for (int i=0; i<vec.size (); ++i) {
for (int j=i+1; j<vec.size (); ++j) {
if (LCM (vec[i], vec[j]) == n) {
ans++;
}
}
}
printf ("%d %d\n", n, ans);
}
return 0;
}
UVA 11752 The Super Powers
只要指数不是素数才可以符合条件，技巧：取对数来求最大的指数
#include <bits/stdc++.h>
typedef unsigned long long ull;
int nprime[105];
bool is_prime(int n) {
int m = (int) sqrt (n + 0.5);
for (int i=2; i<=m; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
ull _pow(ull x, int n) {
ull ret = 1;
while (n) {
if (n & 1) {
ret = ret * x;
}
n >>= 1;
x *= x;
}
return ret;
}
int main() {
int tot = 0;
for (int i=4; i<=64; ++i) {
if (!is_prime (i)) {
nprime[tot++] = i;
}
}
std::map<ull, bool> mp;
int bound = (1 << 16);
for (int i=2; i<=bound; ++i) {
double maxn = log (pow (2.0, 64.0)-1) / log (i);
for (int j=0; j<tot; ++j) {
int n = nprime[j];
if (n >= maxn) {
break;
}
mp[_pow ((ull) i, n)] = true;
}
}
mp[1] = true;
std::map<ull, bool>::iterator it;
for (it=mp.begin (); it!=mp.end (); ++it) {
printf ("%llu\n", it->first);
}
return 0;
}
UVA 11076 Add Again
设有重复元素的全排列数为x，
#include <bits/stdc++.h>
typedef unsigned long long ull;
int main() {
int a[13], cnt[15];
ull f[13];
f[0] = f[1] = 1;
for (int i=2; i<=12; ++i) {
f[i] = f[i-1] * i;
}
int n;
while (scanf ("%d", &n) == 1) {
if (!n) {
break;
}
memset (cnt, 0, sizeof (cnt));
int m = 0;
for (int i=1; i<=n; ++i) {
int x;
scanf ("%d", &x);
if (!cnt[x]) {
a[m++] = x;
}
cnt[x]++;
}
ull sum = 0;
for (int i=0; i<m; ++i) {
ull div = f[cnt[a[i]]-1];
for (int j=0; j<m; ++j) {
if (i != j) {
div *= f[cnt[a[j]]];
}
}
sum += f[n-1] / div * a[i];
}
//printf ("$%llu\n", sum);
ull ans = 0;
for (int i=1; i<=n; ++i) {
ans += sum;
sum *= 10;
}
printf ("%llu\n", ans);
/*
ull tmp = 0;
std::vector<ull> ans;
for (int i=1; i<=n; ++i) {
ans.push_back ((sum + tmp) % 10);
tmp = (sum + tmp) / 10;
}
if (tmp) {
printf ("%llu", tmp);
}
for (int i=ans.size ()-1; i>=0; --i) {
printf ("%llu", ans[i]);
}
puts ("");
*/
}
return 0;
}
UVA 11609 Teams
#include <bits/stdc++.h>
const int MOD = 1e9 + 7;
int pow_mod(int x, int n) {
int ret = 1;
while (n) {
if (n & 1) {
ret = 1ll * ret * x % MOD;
}
n >>= 1;
x = 1ll * x * x % MOD;
}
return ret;
}
int main() {
int T;
scanf ("%d", &T);
for (int cas=1; cas<=T; ++cas) {
int n;
scanf ("%d", &n);
printf ("Case #%d: %d\n", cas, 1ll * pow_mod (2, n - 1) * n % MOD);
}
return 0;
}
POJ 2402 Palindrome Numbers(LA2889)
按照回文串长度分组，找到是第n/num[i]+1组的第n%num[i]-1个位置，因为每组都从1000...0001开始，很容易找到规律。
#include <bits/stdc++.h>
typedef long long ll;
ll num[32];
ll tenp(int m) {
ll ret = 1;
while (m--) {
ret *= 10;
}
return ret;
}
int main() {
ll s = 9;
num[1] = num[2] = s;
for (int i=3; i<31; i+=2) {
s *= 10;
num[i] = num[i+1] = s;
}
int n;
while (scanf ("%d", &n) == 1) {
if (!n) {
break;
}
int i;
for (i=1; i<32 && n > num[i]; ++i) {
n -= num[i];
}
int l = i / 2 + (i & 1);
ll x = tenp (l - 1) + n - 1;
printf ("%I64d", x);
if (i & 1) {
x /= 10;
}
while (x) {
printf ("%d", x % 10);
x /= 10;
}
puts ("");
}
return 0;
}
UVA 11489 Integer Game
除了第一次特判外，接下来只能取3，6，9（保证剩余数字是3的倍数），判断奇偶就可以了。
#include <bits/stdc++.h>
const int N = 1e3 + 5;
char str[N];
int cnt[10];
bool judge() {
memset (cnt, 0, sizeof (cnt));
int sum = 0;
for (int i=0; str[i]; ++i) {
sum += str[i] - '0';
cnt[str[i]-'0']++;
}
bool flag = false;
int t = sum % 3;
for (int i=t; i<10; i+=3) {
if (cnt[i]) {
cnt[i]--;
flag = true;
break;
}
}
if (!flag) {
return false;
}
int tot = cnt[3] + cnt[6] + cnt[9];
return !(tot & 1);
}
int main() {
int T;
scanf ("%d", &T);
for (int cas=1; cas<=T; ++cas) {
scanf ("%s", str);
printf ("Case %d: %c\n", cas, judge () ? 'S' : 'T');
}
return 0;
}
UVA 10791 Minimum Sum LCM
这题题目说的是set集合，不仅仅只是两个数字，结论是所有数字两两互质时最小，即分解质因数后，求
#include <bits/stdc++.h>
long long solve(int n) {
long long ret = 0;
int cnt = 0;
int m = (int) sqrt (n + 0.5);
int nn = n;
for (int i=2; i<=m; ++i) {
if (n % i == 0) {
cnt++;
long long tmp = 1;
while (n % i == 0) {
n /= i;
tmp *= i;
}
ret += tmp;
}
}
if (!cnt || (cnt == 1 && n == 1)) {
return 1ll + nn;
} else {
if (n != 1) {
ret += n;
}
return ret;
}
}
int main() {
int n, cas = 0;
while (scanf ("%d", &n) == 1) {
if (!n) {
break;
}
printf ("Case %d: %lld\n", ++cas, solve (n));
}
return 0;
}
UVA 11461 Square Numbers
前缀思想
#include <bits/stdc++.h>
const int N = 1e5 + 5;
int sum[N];
bool ok(int n) {
int m = (int) sqrt (n);
return m * m == n;
}
void init() {
sum[0] = 0;
for (int i=1; i<=100000; ++i) {
sum[i] = sum[i-1];
if (ok (i)) {
sum[i]++;
}
}
}
int main() {
init ();
int a, b;
while (scanf ("%d%d", &a, &b) == 2) {
if (!a && !b) {
break;
}
printf ("%d\n", sum[b] - sum[a-1]);
}
return 0;
}
UVA 1319 Maximum
都乘以
#include <bits/stdc++.h>
typedef long long ll;
int main() {
int m, p, a, b;
while (scanf ("%d%d%d%d", &m, &p, &a, &b) == 4) {
int sum = a * b;
int x = 0, y = 0;
for (int i=1; i<m; ++i) {
if (sum >= a) {
sum -= a;
x++;
} else {
sum++;
y++;
}
}
double sa = sqrt (a * 1.0);
double ans = y / pow (sa, p) + x * pow (sa, p);
ans += pow (sum / sa, p);
printf ("%d\n", (int) (ans + 0.5));
}
return 0;
}
UVA 1315 Crazy tea party
找规律，靠近1的往1挪，靠近n的往n挪。
#include <bits/stdc++.h>
int main() {
int T;
scanf ("%d", &T);
while (T--) {
int n;
scanf ("%d", &n);
int m = (n - 1) / 2;
int ans = (1 + m) * m;
if (n & 1) {
ans -= m;
}
printf ("%d\n", ans);
}
return 0;
}