解题报告 UVA12716 GCD等于XOR GCD XOR

题意

给定 n,求二元组 (a,b) 满足 1\le a\le b\le n\gcd(a,b)=a \operatorname{xor} b 的个数

思路

假设 a\ge b,注意到 a \operatorname{xor} b=ca \operatorname{xor} c=b。而异或运算相当于一个不进位的加减法,故满足 a-b \le a\operatorname{xor}b\le a+b

a>b 时,\gcd(a,b)=m,则 a=k_1 mb=k_2mk_1> k_2,故 a-b=m(k_1-k_2)>m=\gcd(a,b)

综上,a-b\le gcd(a,b) \le a-b,故 a-b=\gcd(a,b)=a\operatorname{xor} b

由于 m=\gcd(a,b),所以 m\mid a m\mid b。计算时先枚举 m 再枚举 m 的倍数即可。

#include <cstdio>

const int maxn=30000000+5;
long long f[maxn+5];

int main()
{
    int t,n;
    scanf("%d",&t);
    for(int c=1;c<=maxn;++c)
        for(int a=c<<1;a<=maxn;a+=c)
            if((a^(a-c))==c)//即(a^b)==c,b=a-c
                ++f[a];
    for(int i=1;i<=maxn;++i)
        f[i]+=f[i-1];
    for(int kase=1;kase<=t;++kase)
    {
        scanf("%d",&n);
        printf("Case %d: %lld\n",kase,f[n]);
    }
    return 0;
}

解题报告 P1516 青蛙的约会

题目内容

长度为 L 的首尾相接的数轴上有两只青蛙,坐标分别为 xy,分别每次能往前跳 mn 个单位长度,求最少跳几次后相遇。

解题思路

不难得到题目需要我们解如下关于 k 的方程的最小正整数解:

x+km\equiv y+kn\pmod L

化简可得到

(m-n)k\equiv y-x\pmod L

也就是说,我们只要找得到方程

(m-n)k+Lj=y-x

(其中 j\in\mathbb{Z})的最小正整数解,即为答案,而这个方程可以使用拓展欧几里得进行求解。

如果 \gcd(m-n,L)\not|(y-x),说明该方程无解。

为了简化符号表达,接下来令 a=m-nb=Lc=y-xX 为我们要求的 kY 为上文的 j。方程便被化为

aX+bY=c

先使用拓欧求出 aX+bY=\gcd(a,b) 的一个特解 X_0,则该方程的最小正整数解为 X_0\bmod\frac{b}{\gcd(a,b)},最后需要的结果再乘上 \frac{c}{\gcd(a,b)} 即可

输出时注意要避免负数的输出,不开 long long 会炸掉

#include <cstdio>

typedef long long ll;
ll X,Y,M,N,L,gcd;

void exgcd(ll &x,ll &y,ll a,ll b)
{
    if(!b)
        x=1,y=0,gcd=a;
    else
        exgcd(y,x,b,a%b),y-=a/b*x;
}

int main()
{
    scanf("%lld %lld %lld %lld %lld",&X,&Y,&M,&N,&L);
    ll x,y;
    ll a=M-N,c=Y-X,&b=L;
    if(a<0)
        a=-a,c=-c ;
    exgcd(x,y,a,b);
    if(c%gcd)
    {
        printf("Impossible\n");
        return 0;
    }
    printf("%lld\n",(x%(b/gcd)*c/gcd+b/gcd)%(b/gcd));
    return 0;
}

【算法笔记】中国剩余定理(CRT)

是什么

中国剩余定理(孙子定理,Chinese remainder theorem,CRT)是中国古代求解一次线性同余方程组的定理。

怎么用

CRT 可以求解如下的一次线性同余方程组

\begin{cases}
x&\equiv a_1\pmod{m_1} \
x&\equiv a_2\pmod{m_2} \
&\vdots\
x&\equiv a_n\pmod{m_n}\
\end{cases}

其中 m_im_ji,j\in[1,n]i\neq j)要求两两互质。

流程如下:

  1. 计算 \displaystyle M=\prod_{i=1}^nm_i\displaystyle M_i=\frac M {m_i}
  2. 对于每个 M_i,计算其在模 m_i 意义下的逆元 t_i,即 M_it_i\equiv1\pmod{m_i}
  3. 方程组的一个特解 x_0=\displaystyle\sum_{i=1}^na_iM_it_i
  4. 最小正整数解即为 (x_0+M)\bmod M,方程组的解集为 \lbrace x|x=\displaystyle\sum_{i=1}^na_iM_it_i+kM,k\in\mathbb{Z}\rbrace

为什么

下面给出 CRT 的证明:

首先,我们易知 \forall j\in[1,n],当 i\neq j 时有

a_jM_jt_j\equiv 0\pmod{m_i}

i=j 时有

a_iM_it_i\equiv a_iM_iM_i^{-1}\equiv a_i\pmod{m_i}

所以对于我们得到的解 x=\displaystyle\sum_{i=1}^na_iM_it_i,对于任意的 m_i 都有 x\equiv a_i\pmod{m_i},定理得证。

怎么实现

模板题 https://www.luogu.com.cn/problem/P1495

代码实现如下:

#include <cstdio>

typedef long long ll;
ll n,a[15],m[15],Mul,M[16],inv[16],x,y;

void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}

int main()
{
    Mul=1;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld %lld",m+i,a+i);
        Mul*=m[i];
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        M[i]=Mul/m[i];
        x=0,y=0;
        exgcd(M[i],m[i],x,y);
        inv[i]=x<0?x+m[i]:x;
        ans+=a[i]*M[i]*inv[i];
    }
    printf("%lld\n",ans%Mul);
    return 0;
}

模数两两不互质怎么办

使用拓展中国剩余定理那就

【算法笔记】乘法逆元

定义

ax\equiv 1\pmod p

a\perp p (\gcd(a,p)=1)

则称 xa 在模 p 意义下的逆元,可表示为 a^{-1}

费马小定理

假如 a 是一个整数,p 是一个质数,则 a^p-ap 的倍数,表示为

a^p\equiv a\pmod p

a^{p-1}\equiv 1\pmod p

求法一:费马小定理

a^{p-1}\equiv a^{p-2}\cdot a\equiv1\pmod p

即当 p 是质数时,可以直接快速幂求 a^{p-2}\bmod p 即为所求逆元

求法二:拓欧

方程 ax\equiv 1\pmod b 可以转化为 ax+by=1(其中 y 为整数),若保证有解的话说明 \gcd(a,b)=1,我们就可以使用拓展欧几里得算法进行求解。

若题目要求输出最小正整数解,可以将求出来的 x 先加上 b 后对 b 取模。

#include <cstdio>

int a,b;

void exgcd(int &x,int &y,int a,int b)
{
    if(b==0)
    {
        x=1;y=0;
        return;
    }
    exgcd(y,x,b,a%b);
    y-=a/b*x;
}

int main()
{
    scanf("%d %d",&a,&b);
    int x,y;
    exgcd(x,y,a,b);
    printf("%d\n",(x+b)%b);
    return 0;
}

求法三:线性求逆元

p=ki+r,其中 k=\lfloor \frac p i\rfloorr=p\bmod i,且 1。则在模 p 意义下有

ki+r\equiv 0\pmod p

两边同时乘以 r^{-1}i^{-1},则

kr^{-1}+i^{-1}\equiv0\pmod p

移项,

i^{-1}\equiv-kr^{-1}\pmod p

代入 k=\lfloor \frac p i\rfloorr=p\bmod i,有

i^{-1}\equiv -\lfloor \frac p i\rfloor(p\bmod i)^{-1}\pmod p

由于要保证 i^{-1}>0,在最终式子的右边加上 pp\equiv 0\pmod p),最终的式子就是:

i^{-1}\equiv p-\lfloor \frac p i\rfloor(p\bmod i)^{-1}\pmod p

inv[i] 表示 i^{-1} 则递推式如下:

for(int i=2;i<=n;i++)
    inv[i]=(p-p/i)*inv[p%i]%p;

代码(P3811):

#include <cstdio>

typedef long long ll;
const int maxn=3e6+5;
ll n,p;
ll inv[maxn]={0,1};

int main()
{
    scanf("%lld %lld",&n,&p);
    for(ll i=2;i<=n;i++)
        inv[i]=(p-p/i)*inv[p%i]%p;
    for(int i=1;i<=n;i++)
        printf("%lld\n",inv[i]);
    return 0;
}

解题报告 hdu3092 Least common multiple

题目内容

将一个整数 S 拆分,求他们最大的 lcm

解题思路

思路其实比较简单,就是一个完全背包,但是需要注意的细节很多。

第一,发现如果将 s 拆分为 a+b,且 \gcd(a,b) \not=1,则答案为 ab/\gcd(a,b)。相当于 \gcd(a,b) 这一部分就被浪费掉了,所以发现拆分出来的数选择素数或者素数的幂最佳,因为两者间必然互素。解决方案就是在进行 dp 之前先把素数筛一遍。p_i

设我们正在考虑第 i 个素数 p_iq 次方,易得状态转移方程为 f(j)=\max\lbrace f(j),f(j-p_i^q)\times p_i^q\rbrace

第二,我们最后需要的是最大的结果取模,所以如果中间过程中取模的话会出现一些玄学的问题,这个时候就需要对数出来帮忙了。

我们知道如果 ab,则 \log a+\log b<\log c+\log d。所以可以令 f(j) 存储我们取过对数的结果,ans(j) 存储真正的结果。转移方程如下:

f(j)=\max\lbrace f(j),f(j-p_i^q)+ q\log p_i \rbrace\\
ans(j)=\max\lbrace ans(j), ans(j-p_i^q)\times p_i^q \rbrace\bmod m

代码如下:

#include <cstdio>
#include <cmath>

template<class T> T max(T a,T b)
{
    return a>b?a:b;
}

int s,m,ans[3005];
double f[3005];
int prime[500];
bool is_not_prime[3005];



int main()
{
    int cnt=0;
    for(int i=2;i<=3005;i++)
    {
        if(!is_not_prime[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt && prime[j]*i<=3005;j++)
        {
            is_not_prime[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }//欧拉筛
    while(scanf("%d %d",&s,&m)!=EOF)
    {
        for(int i=0;i<=s;i++)
            f[i]=0,ans[i]=1;
        for(int i=1;i<=cnt && prime[i]<=s;i++)
            for(int j=s;j>=prime[i];j--)
            {
                double tmp=log(prime[i]*1.0);//取log
                for(int p=prime[i],q=1;p<=j;p*=prime[i],q++)//取p的q次方
                {
                    if(f[j-p]+q*tmp>f[j])
                    {
                        f[j]=f[j-p]+q*tmp;//更新取了对数的f
                        ans[j]=(ans[j-p]*p)%m;//更新真正答案
                    }
                }
            }
        printf("%d\n",ans[s]);
    }
    return 0;
}

解题报告 P1832 A+B Problem(再升级)(质数和方案)

题目内容

P1832

大意:求 n 被分解成若干个素数之和的方案总数

解题思路

打表出奇迹其实这东西不用完全打表,但是打质数表还是很重要的。

思路就是将 [1,n] 间的质数打出表,然后进行完全背包的求方案数即可,抽象的模型就是有 tot 件物品,每件物品的重量为这个质数的值,然后可以取无限次,求能凑出 n 重量的方案数。

不开 long long 见祖宗

#include <cstdio>
#include <cstring>
typedef long long ll;

const int maxn=1100;
ll n,f[maxn];
bool isprime[maxn];
int tot,prime[maxn];//tot为质数的个数,prime为质数的表。

void make_prime()//埃氏筛即可
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=isprime[0]=0;
    for(int i=2;i<=n;i++)
    {
        if(!isprime[i]) continue;
        for(int j=2;i*j<=n;j++) isprime[i*j]=0;
    }
    for(int i=2;i<=n;i++)
        if(isprime[i])
            prime[++tot]=i;
    return;
}

int main()
{
    scanf("%lld",&n);
    make_prime();
    f[0]=1;//一定记得初始值
    for(int i=1;i<=tot;i++)
        for(int j=prime[i];j<=n;j++)
            f[j]+=f[j-prime[i]];//求方案数的转移方程
    printf("%lld\n",f[n]);
    return 0;
}

解题报告 P1045 麦森数【NOIP2003PJ】

题目内容

P1045

大意:求 2^p-1 的位数和最后 500 位

解题思路

嗯,我的第一思路是爆算(不可能)

蒟蒻发现了求位数可以这样搞:由于 2^p 的各位不可能为 0,所以 2^p 的位数与 2^p-1 的位数相同。又由于一个数的位数为 \lg x+1 ,对 \lg(2^p)+1 进行变换可得

\lg(2^p)+1=p\lg2+1

然后于是第一问 O(1) 解决

第二问一看求 2^p-1 的后五百位,快速幂解决即可,每次操作使用 vector 的 resize() 函数来将多余的删掉即可。每次乘法的时候只乘 500 .

坑点:输出要求前导零和分行输出我因为后面那个调了好久

vector 的 resize 的用法:vector<int>::resize(std::size_t __new_size, const int &__x)意思就是将这个 vector 缩减/增加到能容纳 __new_size 个元素,第二个参数就是将增加出来的赋默认值

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef vector<int> bigint;

bigint operator*(bigint a, bigint b)//高精乘法
{
    bigint ans;
    int la=a.size()>500?500:a.size(),lb=b.size()>500?500:b.size();
    for(int i=0;i<la+lb;i++)
        ans.push_back(0);
    for(int i=0;i<lb;i++)
    {
        for(int j=0;j<la;j++)
        {
            ans[i+j]+=a[j]*b[i];
            if(ans[i+j]>=10)
            {
                ans[i+j+1]+=ans[i+j]/10;
                ans[i+j]%=10;
            }
        }
    }
    for(int i=ans.size()-1;i>0;i--)
    {
        if(ans[i])
            break;
        else
            ans.pop_back();
    }
    if(ans.size()>500)//把多于500的位干掉
        ans.resize(500);
    return ans;
}

bigint ksm(int p)//快速幂
{
    bigint base={2};
    bigint ans={1};
    while(p)
    {
        if(p&1)
            ans=ans*base;
        base=base*base;
        p>>=1;
    }
    ans.resize(500,0);//最后将ans缩到500位并补前导0
    return ans;
}

void print(bigint a)
{
    a[0]--;
    reverse(a.begin(),a.end());
    int j=1;
    for(auto i:a)//c++11 新特性
    {
        printf("%d",i);
        if(j%50==0)//分行输出
            printf("\n");
        j++;
    }
    return;
}

int main()
{
    int p;
    scanf("%d",&p);
    printf("%lld\n",(long long)(p*(double)log10((double)2.0)+1));//搞位数
    bigint ans=ksm(p);
    print(ans);
    return 0;
}

解题报告 P1147 连续自然数和

题目内容

P1147

大意:给定一整数 N ,求所有的区间 [l,r] (l<r) ,使得 l,r\in\mathbb{N}\sum_{i=l}^ri=N

解题思路

这道题就是求连续自然数和等于 N 的所有区间,思路有两种,一种是比较好想的双指针,另一种就是直接枚举 N 的因子。最终双指针更快一些。

双指针:用两个指针 i. j 扫描,求出 [i,j] 的区间和并保持 i\not=j ,当 sum 时,说明少了,将 j 加一,当 sum > N 时,说明多了,将 i 减一,同时记得操作 sum ,如果刚好相等,输出答案并继续枚举。

#include <cstdio>

int main()
{
    int m;
    scanf("%d",&m);
    int sum=1;
    for(int i=0,j=1;i<j&&i<m/2+1;)//只需枚举到m/2即可
    {
        if(sum<m)
            sum+=++j;//小了,j加一,sum同时增加加一后的j
        else if(sum>m)
            sum-=i++;//大了,减一,sum-i然后i加一
        else if(sum==m)
            printf("%d %d\n",i,j),sum-=i++;//打印答案之后记得继续向前枚举
    }
    return 0;
}

枚举因子:由于等差数列可以看作中间项乘以项数,所以完全可以通过枚举 N 的因子判断中间项,然后筛掉不合要求的,项数是偶数时除出来的一定是 .5 结尾的,项数是奇数时一定除得尽。记得特判,具体看代码:

#include <cstdio>
#include <cmath>

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=n;i>1;i--)//i是枚举项数
    {
        if(((!(n%i) && i&1) //如果能整除且项数为奇数
          || (fabs((n/(double)i)-(n/i)-0.5)<1e-5))//或者以.5结尾并且项数为偶数
          && n/(double)i-i/2.0>0)//要求最小项不能越界
        {
            if(fabs((n/(double)i)-(n/i)-0.5)<1e-5)//偶数项
                printf("%d %d\n",n/i-i/2+1,n/i+i/2);//打印左右边界
            else
                printf("%d %d\n",n/i-i/2,n/i+i/2);//奇数项
        }
    }
    return 0;
}

解题报告 P1372 又是毕业季I

题目内容

P1372

大意:在 [1,n] 中选出 k 个数,求这 k 个数的最大的 gcd

解题思路

最近热爱写数论题不知道为什么

思路:当一个数是另一个数的倍数时,他们的 gcd 是其中小的那个数,因此想让 gcd 最大,这些选出来的数字必须满足倍数关系,又由于要选 k 个人,因此选出来人的编号应分别为 \lfloor n/k\rfloor2\lfloor n/k\rfloor3\lfloor n/k\rfloor ……所以最大的 gcd 应为 \lfloor n/k\rfloor。所以答案就是 \lfloor n/k\rfloor,复杂度 O(1)

代码:

#include <cstdio>

int main()
{
    int n,k;
    scanf("%d %d", &n, &k);
    printf("%d\n", n/k);
    return 0;
}