CQUPT 数论+几何 2017/5/22

题解

poj 2142 the balance
题意：
解不定方程 ax+by = n;|x|+|y|最小，当|x|+|y|相等时，|ax|+|by|最小。
思路：
用扩展欧几里得定理。
设d=gcd(a,b)
则x=x0+b/d*t,y=y0-a/d*t
z=|x|+|y|=|x0+b/d*t|+|y0-a/d*t|
实际上就是求z=|a1*t+c1|+|c2-a2*t|在t取何值时最小。(a2>a1)
首先由不定方程ax+by=c,a>0,b>0,c>0可知，x和y只有下述三种情况：
x>0,y< 0; x< 0,y>0; x>0,y>0;
那么对t分类讨论，得出：
1.t< min(-c< c2/a2,z=(a1-a2)t+c1+c2,单调减
3.t> max(-c1/a1,c2/a2),z=(a1+a2)t+c1-c2,单调增
这样，我们知道当z取最小值时，t=c2/a2=y0/(a/d)=y0*d/a 附近
接着只要在t附近几个比较一下取最小值即可。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long mabs(long long a)
{
    return a >= 0 ? a : -a;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if (b == 0)
    {
        x = 1;y = 0;
        return a;
    }
    int r = exgcd(b,a % b,x,y);
    int t = x;
    x = y;
    y = t - a/b*y;
    return r;
}
int main()
{
    int a,b,c;
    while (scanf("%d%d%d",&a,&b,&c) != EOF && a * b *c)
    {
        bool f = 0;
        if (a < b)
        {
            f = 1;
            swap(a,b);
        }
        long long x0,y0;
        long long d;
        d = exgcd(a,b,x0,y0);
        x0 = x0 * c / d;
        y0 = y0 * c / d;
        long long z = mabs(x0) + mabs(y0);
        long long anx = mabs(x0),any = mabs(y0);
        long long t = y0 * d / a;
        for (int i = t - 5;i <= t + 5;i++)
        {
            long long tx = x0 + b / d * i,ty = y0 - a / d * i;
            long long tz = mabs(tx) + mabs(ty);
            if (tz < z)
            {
                z = tz;
                anx = mabs(tx);
                any = mabs(ty);
            }
        }
        if (f)
            printf("%I64d %I64d\n",any,anx);
        else
            printf("%I64d %I64d\n",anx,any);
    }
    return 0;
}

poj 1830 开关问题
思路：
高斯消元。
求的时自由变量的个数，每个自由变量有0，1两种情况，所以答案是ans << 1。
ma[i][j]表示j灯的状态是否会影响i灯的状态，s是开始状态，e是结束状态，根据异或的可逆性，可以将开始和结束异或，然后求ma矩阵的秩，就是线性代数的那一套。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int s[35],e[35];
int orz[35];
int ma[35][35];
int mabs(int pp)
{
    return pp >= 0 ? pp : -pp;
}
int main()
{
    int k;
    scanf("%d",&k);
    while (k--)
    {
        memset(s,0,sizeof(s));
        memset(e,0,sizeof(e));
        memset(ma,0,sizeof(ma));
        memset(orz,0,sizeof(orz));
        int n;
        scanf("%d",&n);
        for (int i = 1;i <= n;i++)
            scanf("%d",s+i);
        for (int i = 1;i <= n;i++)
            scanf("%d",e+i);
        for (int i = 1;i <= n;i++)
            orz[i] = s[i] ^ e[i];
        int a,b;
        while (scanf("%d%d",&a,&b) == 2)
        {
            if (!(a*b)) break;
            ma[b][a] = 1;
        }
        for (int i = 1;i <= n;i++) ma[i][i] = 1;
        for (int i = 1;i <= n;i++)
            ma[i][n+1] = orz[i];
        for (int i = 1;i <= n;i++)
        {
            int t = i;
            for (int j = i+1;j <= n;j++)
                if (mabs(ma[j][i]) > mabs(ma[t][i])) t = j;
            if (t != i)
            {
                for (int j = 1;j <= n+1;j++) swap(ma[i][j],ma[t][j]);
            }
            if (ma[t][i] == 0) continue;
            for (int j = i + 1;j <= n;j++)
            {
                if (ma[j][i] == 0) continue;
                for (int l = i;l <= n + 1;l++)
                    ma[j][l] ^= ma[i][l];
            }
        }
        int r1 = 0,r2 = 0;
        for (int i = 1;i <= n;i++)
        {
            bool f1 = 0,f2 = 0;
            for (int j = 1;j <= n;j++)
                if (ma[i][j]) f1 = 1;
            for (int j = 1;j <= n + 1;j++)
                if (ma[i][j]) f2 = 1;
            if (f1) r1++;
            if (f2) r2++;
        }
        if (r1 == r2 && r1 == n) printf("1\n");
        else if (r1 < r2) printf("Oh,it's impossible~!!\n");
        else if (r1 == r2) printf("%d\n", 1 << (n - r2));
    }
    return 0;
}

hdu 5446 unknown treasure
题意：
从n个苹果中选择m个，并且结果对M取余，M是很多个质数的乘积。‘
思路：
首先，求组合数，可以用卢卡斯定理，把对每一个质数取余的结果保存下来，之后用中国剩余定理合并。在中国剩余定理的时候，由于long long会爆炸，所以运用了按位乘的方法。
代码：

#include <stdio.h>
#include <string.h>
typedef long long ll;
ll cs[15],ys[15];
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if (b == 0)
    {
        x = 1;y = 0;
        return a;
    }
    ll r = exgcd(b,a % b,x,y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return r;
}
ll cal(ll a,ll b,ll p)
{
    a = (a % p + p) % p;
    b = (b % p + p) % p;
    ll ans = 0;
    for (ll i = 1;i;i <<= 1)
    {
        //printf(")))))\n");
        if (b & i)
            ans = (ans + a) % p;
        a <<= 1;
        a %= p;
    }
    return ans;
}
ll quick_mod(ll a,ll b,ll p)
{
    if (b == 0) return 1;
    ll x = quick_mod(a,b / 2,p);
    ll ans = x * x % p;
    if (b % 2) ans = ans * a % p;
    return ans;
}
ll inv(ll a,ll b)
{
    ll x,y;
    exgcd(a,b,x,y);
    return (x % b + b) % b;
}
ll C(ll n,ll m,ll p)
{
    if (m > n) return 0;
    ll ans = 1;
    ll a = 1,b = 1;
    for (int i = 1;i <= m;i++)
    {
        b *= i;
        b %= p;
        a *= (n - i + 1);
        a %= p;
    }
    return cal(a,inv(b,p),p);
}
ll Lucas(ll n,ll m,ll p)
{
    if (m == 0) return 1;
    else
        return C(n % p,m % p,p) * Lucas(n / p,m / p,p) % p;
}
ll China(int cnt)
{
    ll sum = 1;
    ll ans = 0;
    for (int i = 0;i < cnt;i++)
    {
        sum *= cs[i];
    }
    for (int i = 0;i < cnt;i++)
    {
        ll tt = sum / cs[i];
        ll x,y;
        exgcd(tt,cs[i],x,y);
        ll ans1 = cal(x,ys[i],sum);
        ll ans2 = cal(ans1,tt,sum);
        ans = (ans2 + ans) % sum;
    }
    return (ans%sum + sum) % sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(cs,0,sizeof(cs));
        memset(ys,0,sizeof(ys));
        long long n,m;
        scanf("%I64d%I64d",&n,&m);
        int num;
        scanf("%d",&num);
        for (int i = 0;i < num;i++)
        {
            ll tt;
            scanf("%I64d",&tt);
            cs[i] = tt;
            ys[i] = Lucas(n,m,cs[i]);
        }
        long long ans = China(num);
        printf("%I64d\n",ans);
    }
    return 0;
}