解题报告 P2822 组合数问题

题目内容

P2822

大意:给定 tkt 次给出 nm,询问所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right ) 有多少对 (i,j) 满足 k|\binom{i}{j}

解题思路

因为数据范围中 n,m\leq 2000,所以不能直接把组合数存储起来,而注意到一个数据点中 k 是固定的,因此可以定义 f_{i,j} 为对于所有的 x\in[0,i]y\in[0,\min(j,x)] 中满足 k|\binom x y\binom x y 的个数。

可以使用递推法预处理所有的 \binom i j\bmod k,然后使用二维前缀和来处理 f_{i,j},每次 O(1) 回答询问。

c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];//下面解释
    }

上面是处理 f 的部分。每次求出组合数直接取模方便判断是否能被 k 整除。二维前缀和的递推都很容易看懂,但是对于最后的 f[i][i+1]=f[i][i]; 的理解是:由于每次 f[i][j] 都要加上 f[i-1][j],而不处理最后的 f[i][i+1] 的话会造成处理下一排时 f[i-1][j] 为 0,所以要进行这样的处理。

还有就是数据中可能有 n,这时候要进行特判

完整代码:

#include <cstdio>
#include <cctype>

//快读

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];
    }
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m>n?n:m]);
    }
    return 0;
}

当然还有另一种方法就不需要特判,如下:

#include <cstdio>
#include <cctype>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]%k+c[i-1][j]%k)%k;
    for(int i=1;i<=2000;i++)
        for(int j=1;j<=2000;j++)
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(i>=j && c[i][j]==0);
    //这里和上面一样,但是一定要注意判断这里的c[i][j]有没有意义,否则会抱灵
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m]);
    }
    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;
}

解题报告 P1865 A % B Problem(区间质数)

题目内容

P1865

大意:求区间质数个数

解题思路

第一眼看上去想到线段树,但其实这题可以使用前缀和的思想来做,令 a_x 表示在 [1,x] 中有 a_x 个质数,当查询 [l,r] 的质数个数时,只需打印 a_r-a_{l-1} 即可。

前面要先筛出质数,由于我不会欧拉筛所以用的是埃氏筛,虽然慢了点,但是能过去。

代码:

#include <cstdio>
#include <cstring>
#include <cmath>

int n,m;//m is the range
bool prime[1000005];
int qzh[1000005];

void make_prime()
{
    memset(prime,1,sizeof(prime));
    prime[0]=prime[1]=0;
    for(int i=2;i<=sqrt(m)+1;i++)
    {
        if(prime[i])
            for(int j=2*i;j<=m;j+=i)
                prime[j]=0;
    }
    return;
}

int main()
{
    scanf("%d %d", &n, &m);
    make_prime();//不要忘记先造质数
    for(int i=0;i<=m;i++)
    {
        qzh[i]=qzh[i-1];
        if(prime[i])
            qzh[i]++;
    }
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d %d", &l, &r);
        if(l<1||r>m)//注意判别边界
            printf("Crossing the line\n");
        else
            printf("%d\n",qzh[r]-qzh[l-1]);//输出前缀和之差
    }
    return 0;
}

解题报告 P1403 [AHOI2005]约数研究

题目内容

P1403

大意:令 \tau(x) 表示正整数 x 的正约数个数,求 \sum_{i=1}^n\tau(x)

解题思路

暴力:枚举每个数的所有因数个数然后加起来即可,时间复杂度 O(n\sqrt n),光荣 T 三个点

先放公式:

\sum_{i=1}^n\tau(x)=\sum_{i=1}^n\frac n i

原理:在区间 [1,n] 中,有 1 这个约数的数有 n/1 个,有 2 这个约数的数有 n/2 个,… 有 i 为约数的数有 n/i 个,所以跑一次 O(n) 统计答案即可。

这代码真尼玛短

#include <cstdio>

int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        ans+=n/i;
    printf("%d\n",ans);
    return 0;
}

解题报告 P1029 gcd 和 lcm 问题

题目内容

P1029

大意:给出 x_0, y_0 ,求出满足 \gcd(P,Q)=x_0,\operatorname{lcm}(P, Q)=y_0P,Q 的个数

解题思路

挨个枚举即可,从 x_0 枚举到 y_0 ,具体思路是以下关系:

\gcd(a,b)\times\operatorname{lcm}(a,b)=\lvert ab\rvert

算出枚举到的 \gcd 然后用 x_0y_0 去除判断 lcm 是否符合条件即可。这题的数据范围理论上可以爆 int 但是他没有爆。管他的代码规范最重要。

下面的代码可以优化,但是我不想再优化了,老是 WA

#include <cstdio>
#include <cmath>
typedef unsigned long long ll;

ll gcd(ll x, ll y)
{
    if(!y) return x;
    return gcd(y,x%y);
}

int main()
{
    ll x0,y0;
    scanf("%llu %llu",&x0,&y0);
    ll prod=x0*y0,ans=0;//x_0y_0
    for(ll i=x0;i<=y0;i++)
    {
        if(!(prod%i))
        {
            ll gcdcur=gcd(i,prod/i);
            if(gcdcur==x0 && prod/gcdcur==y0)
                ans++;
        }
    }
    printf("%llu\n",ans);
    return 0;
}

解题报告 P2152 [SDOI2009]SuperGCD

题目内容

P2152

高精求两数 gcd

解题思路

使用辗转相除法求gcd的话不仅不方便实现高精,而且容易 T ,所以这里使用更相减损术。

老祖宗的方法真香

具体思路:

\begin{aligned}
\gcd(a,b)&=2\gcd(a/2,b/2)\quad&(2\mid a, 2\mid b)\
\gcd(a,b)&=\gcd(a/2,b)\quad&(2\mid a,2\not\mid b)\
\gcd(a,b)&=\gcd(a-b,b)\quad&(2\not\mid a,2\not\mid b,a>b)
\end{aligned}

依次解下去就可了,注意高精即可,代码有点麻烦,不要用递归容易爆栈

这题我一开始提交的时候莫名RE,结果发现是判断函数cmp写挂了,表示绝望调了好久qwq。

#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>
using namespace std;

typedef vector<int> bigint;
bigint _minus(bigint, bigint);
bigint _times(bigint, bigint);
void div2(bigint&);
void print(bigint);
inline bool isodd(bigint&);

bigint _minus(bigint a, bigint b)//高精减法
{
    for(int i=0;i<b.size();i++)
    {
        a[i]=a[i]-b[i];
        if(a[i]<0)
        {
            a[i+1]--;
            a[i]+=10;
        }
    }
    for(int i=b.size();i<a.size();i++)
    {
        if(a[i]<0)
            a[i+1]--,a[i]+=10;
    }
    for(int i=a.size()-1;i>0;i--)
    {
        if(a[i])
            break;
        if(!a[i])
            a.pop_back();
    }
    return a;
}

bigint _times(bigint a, bigint b)//高精乘法
{
    bigint ans;
    int la=a.size(),lb=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();
    }
    return ans;
}

void div2(bigint &a)
{
    for(int i=a.size()-1;i>=0;i--)
    {
        if(a[i]&1)
            a[i-1]+=10;
        a[i]/=2;
    }
    if(!a.back())
        a.pop_back();
}

bigint read()
{
    bigint ans;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        ans.push_back(c-'0');
        c=getchar();
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

void print(bigint a)
{
    for(int i=a.size()-1;i>=0;i--)
        printf("%d",a[i]);
    printf("\n");
    return;
}

inline bool isodd(bigint &a)//判断其是否为奇数
{
    return a.front()&1;
}

bool cmp(bigint a, bigint b)//return a>b
{
    if(a.size()>b.size())
        return true;
    else if(a.size()<b.size())
        return false;
    else
    {
        for(int i=a.size()-1;i>=0;i--)
            if(a[i]>b[i])
                return true;
            else if(a[i]!=b[i])
                return false;
    }
    return false;
}

int main()
{
    bigint a=read(),b=read();
    bigint tag={1},two={2};
    while(a!=b)//当a=b时zhong
    {
        if(!isodd(a) && !isodd(b))
        {//如果都是偶数那就都除以二然后标签乘二
            div2(a);
            div2(b);
            tag=_times(tag,two);
        }
        else if(!isodd(a))//如果a是偶数
            div2(a);//除以二
        else if(!isodd(b))//如果b是偶数
            div2(b);//除以二
        else
        {
            if(cmp(a,b))//判断哪个更大然后辗转相减
                a=_minus(a,b);
            else
                b=_minus(b,a);
        }
    }
    print(_times(a,tag));//返回的是最终结果乘上tag
    return 0;
}