训练指南第二章-基础问题 P170

	/	Problem A
	/	Problem B
	/	Problem C
	/	Problem D
	/	Problem E
	/	Problem F
	/	Problem G
	/	Problem H
	/	Problem I
	/	Problem J
	/	Problem K
	/	Problem L
		Problem M
	/	Problem N

 

 

 

 

 

 

 

 

 

 

 

 

 

 

UVA 11388 GCD LCM

显然在合理的情况下，a=G，b=L

#include 
     
      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

解法一：分解质因数，因为,,，所以在ai小于最大值时bi为最大值，否则为0.

解法二：数学方法，tb=C/A，当g=GCD(A, tb) != 1，a /= g. tb *= .（不是很懂）

#include 
     
      void get_prime(int n, std::map
      
        &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
       
         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
        
         ::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 
     
      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 
     
      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
      
       = 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 
     
      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 
     
      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
      
        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
      
     

UVA 11752 The Super Powers

只要指数不是素数才可以符合条件，技巧：取对数来求最大的指数

#include 
     
      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
      
        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
       
        = maxn) {                break;            }            mp[_pow ((ull) i, n)] = true;        }    }    mp[1] = true;    std::map
        
         ::iterator it;    for (it=mp.begin (); it!=mp.end (); ++it) {        printf ("%llu\n", it->first);    }    return 0;}
        
       
      
     

UVA 11076 Add Again

设有重复元素的全排列数为x，，所以，不考虑位置的话，总和为,然后考虑进位累加的问题。

#include 
     
      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
      
        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 
     
      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 
     
      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 
     
      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 
     
      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 
     
      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

都乘以。，。因为p是偶数，贪心思想一些数取-1，一些取a，还有一个在范围内。

#include 
     
      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
      
       = 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 
     
      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;}