ACM – Uva10375 – 组合数公式

 发表于 May 2, 2015  |  1 分钟  |  198 个字  |  svtter

有些匪夷所思的题目。。注释部分加上就WA，不加就AC。。

推公式，因为$$C(n,k) = C(n,k-1) * (n-k+1)/k$$

所以$$ans = \frac{C(n, k)}{C(r, s)}\qquad$$改成递推即可。

#include <bits/stdc++.h>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int p, q, r, s;
    double ans = 1.0;
    while(scanf("%d%d%d%d", &p, &q, &r, &s) != EOF)
    {
        ans = 1.0;
        // if(p - q > q) q = p - q;
        // if(r - s > s) s = r - s;
        for(int i = 1; i <= q || i <= s; i++)
        {
            if(i <= q) ans = ans * (p-i+1) / i;
            if(i <= s) ans = ans * i / (r-i+1);
        }
        printf("%.5lf\n", ans);
    }
    return ;
}

ACM – UVA11029 – 快速幂，快速前幂

 发表于 May 2, 2015  |  2 分钟  |  233 个字  |  svtter

后面的三位快速幂即可，但是前面三位不好求。经过分析，每一位都有可能牵扯到前三位的值，因此无法具体的作出判断。

如果使用模方法省去后面的部分，必定会造成误差，随着省略的部分增多，误差积累势必会越来越大。（错了一组数据）

最佳的方法还是数学分析（参考了题解）：

分析n，$a = log_{10}^n$，则$n = a ^ {10}$。分解a = i + d，i为正数部分，d为小数部分。那么i影响的仅仅是位数，d影响的则是具体的数字。

这样得到的值是准确的。另外对浮点数取余

fmod(double, mod)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll unsigned long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int pow_mod(int x, int k, int p)
{
    int ans = 1;
    x %= p;
    while(k)
    {
        if(k&1) ans = ans * x % p;
        x = x * x % p;
        k >>= 1;
    }
    return ans;
}
int solve(int n, int k)
{
    double d = log10(n*1.0);
    int ans = (int)pow(10, 2 + fmod(k*d, 1));
    return ans;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int T;
    int n, k;
    cin >> T;
    while(T--)
    {
        scanf("%d%d", &n, &k);
        int ans2 = pow_mod(n, k, 1000);
        int ans1 = solve(n, k);
        printf("%d...%03d\n", ans1, ans2);
    }
    return ;
}

ACM – UVA10820 – 欧拉函数

 发表于 May 1, 2015  |  1 分钟  |  212 个字  |  svtter

给出一个Answer(x,y)函数，x,y属于[1,N]，$Answer(k_x, k_y)$可以由Answer(x,y)得出，目的是求需要计算多少Answer(x,y)。

就是求1,N范围的欧拉函数的加和。欧拉函数的定义是与N互质的数的个数，所以需要如此计算。一开始没有发现就是求欧拉惭愧惭愧。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
const int maxn = 1e5 + 10;
int phi[maxn];
void phi_table(int n)
{
    memset(phi, , sizeof(phi));
    phi[1] = 1;
    for(int i = 2; i <= n; i++) if(!phi[i])
        for(int j = i; j <= n;j += i)
        {
            if(!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i-1);
        }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int N;
    phi_table(maxn-1);
    ll ans;
    while(scanf("%d", &N), N)
    {
        ans =;
        for(int i = 1; i <= N;i ++)
            ans += phi[i];
        ans = ans *2 - 1;
        printf("%lld\n", ans);
    }
    return ;
}

ACM – UVA571 – 模方程

 发表于 May 1, 2015  |  2 分钟  |  223 个字  |  svtter

一开始在扩展gcd上想了许久没有办法将得出的数字直接转换成为相应的输出，后来发现就是模方程。

因为不求最佳解，所以直接使用ca*x = n (mod cb)即可。这个方程的解可以覆盖全部的n，因为该方程如果有解，则n是gcd(ca, cb)的倍数。因为ca, cb互质 gcd (ca, cb) = 1，所以明显通过单纯的加满B，向A中倒，然后清空A就可以遍历所有n的解（尽管可能不是最佳解）。

不能是cb*x = n (mod ca)，因为n可能大于ca.

如果求最佳解，显然是bfs。当然这到题目也可以dfs来做，不过明显要复杂很多。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int ca, cb, n;
    while(scanf("%d%d%d", &ca, &cb, &n) != EOF)
    {
        //解模方程 ax = n(mod b)
        int a = , b = ;
        while(b != n)
        {
            if(a == )
            {
                puts("fill A");
                a = ca;
            }
            if(b == cb)
            {
                puts("empty B");
                b = ;
            }
            if(a > cb - b)
            {
                a = a - (cb-b);
                b = cb;
            }
            else
            {
                b += a;
                a = ;
            }
            puts("pour A B");
        }
        puts("success");
    }
    return ;
}

ACM – Uva10717 – lcm+dfs

 发表于 April 29, 2015  |  2 分钟  |  364 个字  |  svtter

今天不适合刷题。。。

题意：一个桌子4条腿，每条腿由一种硬币构成，四条腿必须一样长，请问如何最接近给出的标准桌子高度，输出两个最接近的值。

更新两个值的时候错误的判断如果lcm大于h就不再更新了，却没有想到高于h的部分依然可以更新，只是不能更新小于h的部分了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int gcd(int a, int b)
{
    return b == ? a: gcd(b, a % b);
}
const int maxn = 50 + 10;
int a[maxn];
int n, t;
int table[15];
int ans1[15];
int ans2[15];
void output()
{
    for(int i = ; i < t; i++)
        printf("%d %d\n", ans1[i], ans2[i]);
}
// 寻找边界
bool findmax(int lcm, int num, int &mint, int &maxt)
{
    // if(lcm > num)
    // return false;
    int t = num / lcm * lcm;
    if(t == num)
    {
        mint = num;
        maxt = num;
    }
    else
    {
        mint = t;
        maxt = t + lcm;
    }
    // return 1;
}
// 检查
void check(int lcm)
{
    int mint, maxt;
    for(int i = ; i < t; i++)
    {
        findmax(lcm, table[i], mint, maxt);
        if(ans1[i] == -1 || mint > ans1[i]) ans1[i] = mint;
        if(ans2[i] == -1 || maxt < ans2[i]) ans2[i] = maxt;
    }
}
// 枚举四个腿
void fs(int c, int num, int lcm)
{
    if(num == 4)
    {
        check(lcm);
        return;
    }
    for(int i = c; i < n; i++)
    {
        int temp = lcm;
        lcm = lcm / gcd(lcm, a[i]) * a[i]; // 可能溢出
        fs(i+1, num+1, lcm);
        lcm = temp;
    }
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    while(~scanf("%d%d", &n, &t) && n != )
    {
        for(int i = ; i< n; i++) scanf("%d", &a[i]);
        for(int i = ; i < t; i++)
        {
            scanf("%d", &table[i]);
            ans1[i] = -1;
            ans2[i] = -1;
        }
        fs(, , 1);
        output();
    }
    return ;
}

ACM – UVa10791 – divide prime

 发表于 April 29, 2015  |  2 分钟  |  222 个字  |  svtter

谢天谢地终于过了。

就是求分解质因数后的和，如果是质数那么返回1+n本身。

  1. 一开始直接暴力求两个质因数的情况，铁定不对啊。。
  2. 第二次发现策略有问题，转为使用枚举质因数，然后发现仅仅是质因数LCM有问题啊。。
  3. 第三次没有考虑质数
  4. 第四次没有考虑Case
  5. 第五次不记得了。
  6. 第七次AC，哭了真是。。一定要先分析好题目啊。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define inf 0x3f3f3f3f
#define ll long long int
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(b, -1, sizeof(b))
#define deb(x, n) cout << (x) << " " << (n) << endl
#define cr printf("\n")
// 调试用
    template <class type>
void debug(type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
ll solve(int n)
{
    if(n == 1) return 2;
    ll ans = ;
    ll sq = sqrt(n);
    int cnt, pf = ;
    for(ll i = 2; i <= sq;i++)
    {
        if(n % i == )
        {
            cnt = 1;
            while(n % i == )
            {
                cnt *= i;
                n /= i;
            }
            pf ++;
            ans += cnt;
        }
    }
    if(1 != n)
    {
        ans += n;
        pf++;
    }
    // n为质数
    if(pf <= 1) ans ++;
    return ans;
}
int main()
{
#ifdef debug
    // freopen("input", "r", stdin);
#endif
    int n;
    int c = 1;
    // const int maxn = pow(2, 31) -1;
    // printf("%d\n", maxn);
    ll ans;
    while(scanf("%d", &n) && n)
    {
        ans = solve(n);
        printf("Case %d: ", c++);
        printf("%lld\n", ans);
    }
    return ;
}

ACM – Uva106 – 勾股定理

 发表于 April 28, 2015  |  2 分钟  |  305 个字  |  svtter

從維基百科的勾股數條目參考來的通解：

給一個任意數對(X,Y)，用以下公式代替

$A = X^2 – Y^2$

$B = 2XY$

$C = X^2 + Y^2$

得出的A,B,C就是一組勾股數。

若 (X,Y) 恰好互質而且一奇一偶，那麼會得到一組(A,B,C)互質的勾股數。

知道通解後，雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。

按照台湾同胞的题解。 — 勾股数公式也是很神奇的啊。。。

此外还学习了bitset，因为是按位存储，所以比一般的bool来的更加迅速，也更加节省时间。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int gcd(int a, int b) { return a % b ==  ? b : gcd(b, a%b); }
int odd(int a, int b) {
    return (a%2 && !(b%2)) || (b%2 &&!(a%2));
}
int judge(int a, int b)
{
    return (gcd(a, b) == 1 && odd(a, b));
}
int n;
const double eps = 1e-15;
const int N = 1e6+10;
bitset <N> p;
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    while(~scanf("%d", &n))
    {
        p.set();
        int cnt = ;
        for(int x = 1; x < 1000; x ++)
            for(int y = x+1; ; y += 2)
            {
                int a, b, c;
                if(judge(x, y))
                {
                    a = y*y - x*x;
                    b = 2*x*y;
                    c = y*y + x*x;
                    if(c > n) break;
                    cnt ++;
                    int ta = a, tb = b, tc = c;
                    while(tc <= n)
                    {
                        p[ta] = p[tb] = p[tc] = ;
                        ta += a, tb += b, tc += c;
                    }
                }
            }
        int c2  = ;
        for(int i = 1;i <= n; i++)
            if(p[i]) c2++;
        printf("%d %d\n", cnt, c2);
    }
    return ;
}

ACM – Uva10673 – 扩展gcd

 发表于 April 28, 2015  |  3 分钟  |  461 个字  |  svtter

水题一发。。直接使用floor和ceil函数，然后暴力即可。。。

如果使用快速的方法，就是扩展gcd。其中d的初始值没有关系，最后返回的是gcd(a,b).

暴力算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
// ax + by = d
// 扩展gcd
void gcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if(!b) { d = a; x = 1; y = ; }
    else { gcd(b, a%b, d, y, x);  y-= x*(a/b);  }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int T;
    cin >> T;
    ll x, k;
    while(T--)
    {
        scanf("%lld%lld", &x, &k);
        double c = x/(double)k;
        ll fl = floor(c);
        ll ce = ceil(c);
        // printf("%lld %lld\n", a, b);
        bool find = ;
        for(ll i = ; !find; i++)
            for(ll j = ; i * fl + j *ce <= x; j++)
            {
                if(i*fl + j *ce == x)
                {
                    printf("%lld %lld\n", i, j);
                    find =1;
                    break;
                }
            }
    }
    return ;
}

扩展gcd算法

速度更快，0.012

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
// ax + by = d
// 扩展gcd
void gcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if(!b) { d = a; x = 1; y = ; }
    else { gcd(b, a%b, d, y, x);  y-= x*(a/b);  }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int T;
    cin >> T;
    ll x, k;
    while(T--)
    {
        scanf("%lld%lld", &x, &k);
        double c = x/(double)k;
        ll fl = floor(c);
        ll ce = ceil(c);
        ll a1, a2, g;
        gcd(fl, ce, g, a1, a2);
        a1 *= x/g;
        a2 *= x/g;
        printf("%lld %lld\n", a1, a2);
    }
    return ;
}

ACM – UVA11121 – 进制

 发表于 April 28, 2015  |  1 分钟  |  6 个字  |  svtter

题意是由10进制转换成-2进制，但是明显我分析错了，所以写了调了接近一下午的bug。。。

有时间再写正常的题解。

题解：

如果当前数位和输入n符号相同，那么不做处理，如果不同且为1，那么下一位（即左边一位）做+1处理 — 因为下一位是上一位的2倍，就相当于做一个变号处理。

ACM – 莫比乌斯反演

 发表于 April 27, 2015  |  1 分钟  |  68 个字  |  svtter

昨天卡了这道题目，今天特意来看看莫比乌斯反演。

title

其中，$∑_{d|n}$含义为整除.

ACdreamer大大的讲解

看了这篇文章即可= =

wikipedia的公式:

title

title

以上就是具体的公式，此外，还有线性筛法:

void Init()
{
    memset(vis,,sizeof(vis));
    mu[1] = 1;
    cnt = ;
    for(int i=2; i<N; i++)
    {
        if(!vis[i])
        {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j=; j<cnt&&i*prime[j]<N; j++)
        {
            vis[i*prime[j]] = 1;
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];
            else
            {
                mu[i*prime[j]] = ;
                break;
            }
        }
    }
}

这段代码也是摘自AC大大。我们得到这个东西有什么用？

简单来说，就是简化计算数论函数和的计算的过程，进行加速。

在HDU5212中，给出的题解是：

这道题需要一些莫比乌斯反演、线性筛的知识

定义$f(x)=x∗(x−1)$

题目所求即为$\Sigma(f(gcd(ai,aj)|i!=j,1≤i,j≤n)$

先用线性筛求出miu在[1,10000]的函数值

利用莫比乌斯反演公式我们可以$O(vlogv)$暴力求解出函数g（就是$f(n)/miu$）在[1,10000]的函数值，其中g满足：

$\Sigma(g(d)|x)$

这样所求答案即为：

$\Sigma(g(d)∗cnt(d)∗cnt(d)|1≤d≤10000)$，其中cnt函数满足：

cnt(x)=在a1,a2,..,an中是x的倍数的个数

而cnt的取值也可以$O(vlogv)$暴力计算出

所以总的时间复杂度就是$O(vlogv)$的

就是这样。