/ Vijos / 题库 / 猩猩散步 /

题解

53 条题解

  • 2
    @ 2018-08-16 17:05:51

    #include<iostream>
    #include <cstring>

    using namespace std;

    const long a[66]= {0 ,2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,
    29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,
    71 ,73 ,79 ,83 ,89 ,97 ,101,103,107,109,
    113,127,131,137,139,149,151,157,163,167,
    173,179,181,191,193,197,199,211,223,227,
    229,233,239,241,251,257,263,269,271,277,
    281,283,293,307,311,313};

    void mul(long a[1000],long n)
    { long i;
    for (i=1; i<=a[0]; i++)
    a[i]=a[i]*n;
    for (i=1; i<a[0]; i++) {
    a[i+1]+=a[i]/10;
    a[i]%=10;
    }
    while (a[a[0]]>9) {
    a[a[0]+1]=a[a[0]]/10;
    a[a[0]]%=10; a[0]++;
    }
    if (a[0]>101)
    a[0]=101;
    }

    int main(){
    long i,j,n,m,all,h[200000],nn,mm,ans[1000];
    scanf("%ld %ld",&n,&m);
    all = n + m;
    memset(h,0,sizeof(h));
    for (i = n+1; i <= all; i++)
    {
    nn=i;
    for (j = 1; j <= 65; j++)
    {
    while (nn%a[j] == 0)
    {h[a[j]]++; nn/=a[j];
    if (nn==1)
    break;}
    if (nn==1)
    break;}
    if (nn!=1)
    h[nn]++;
    }
    for (i=1; i<=m; i++)
    {
    mm=i;
    for (j=1; j<=65; j++)
    {
    while (mm%a[j]==0)
    {h[a[j]]--; mm/=a[j];
    if (mm==1)
    break;}
    if (mm==1)
    break;}
    if (mm!=1)
    h[mm]--;
    }
    ans[0]=1;
    ans[1]=1;
    for (i=1; i<=100000; i++)
    while (h[i]>0) {
    mul(ans,i);
    h[i]--;
    }
    for (i=100; i>=1; i--) {
    printf("%ld",ans[i]);
    if (i%10==1)
    printf("\n");
    }
    }
    c++代码，已AC

  • 1
    @ 2022-04-11 14:49:54

    打表YYDS

  • 0
    @ 2020-05-13 21:20:10 
    #include<bits/stdc++.h>
using namespace std;
long long x,k,ans=1,s=0,l=0;
int a[100005];
bool prime[100005];
int p[1000005];
void mu(int q) 
{
    for(int i=1;i<=l;i++)
    p[i]=p[i]*q;
    int i=1;
    while(i<=l||p[i]>10)
    {
        p[i+1]=p[i+1]+p[i]/10;
        p[i]=p[i]%10;
        i++;
    }
    l=i;
    while(!p[l]) 
    l--;
}
void mu2(int q)
{
    for(int i=1;i<=sqrt(q)+1;i++)
    { 
        if(prime[i])
        { 
            while(q%i==0)
            {
                a[i]++;
                q=q/i;
            }
        } 
    } 
    if(q>0) 
    a[q]++;
}
void di(int q)
{
    for(int i=1;i<=sqrt(q)+1;i++)
    { 
        if(prime[i])
        { 
            while(q%i==0)
            {
                a[i]--;
                q=q/i;
            }
        }
    } 
    if(q>0) 
    a[q]--;
}
int main()
{
    p[1]=1;
    l=1;
    cin>>k>>x;
    ans=k+x;
    for(int i=2;i<=ans;i++)
    prime[i]=true;
    for(int i=2;i<=ans;i++)
    { 
        if(prime[i])
        {
            for (int j=i;j<=ans/i;j++)
            prime[i*j]=false;
        } 
    }
    for(int i=1;i<=min(k,x);i++)//ans*(ans-1)*……min(k,x) 
    mu2(ans-i+1);
    for(int i=1;i<=min(k,x);i++)//min(k,x)!
    di(i);
    for(int i=1;i<=ans;i++) 
    {
        for(int j=1;j<=a[i];j++)
        mu(i);
    } 
    for(int i=100;i>=1;i--)
    { 
        if(i%10!=1)
        cout<<p[i];
        else
        cout<<p[i]<<endl;
    } 
    return 0;
}

    AC代码

  • 0
    @ 2013-10-27 18:53:44

    公式大家应该都知道，很明显的组合。
    主要是写个分解质因数，大问题没有。
    dxe—SYF

  • 0
    @ 2012-08-13 21:41:53

    ├ 测试数据 01：答案正确... (103ms, 972KB)

    ├ 测试数据 02：答案正确... (56ms, 972KB)

    ├ 测试数据 03：答案正确... (48ms, 972KB)

    ├ 测试数据 04：答案正确... (75ms, 972KB)

    ├ 测试数据 05：答案正确... (40ms, 972KB)

    ├ 测试数据 06：答案正确... (83ms, 972KB)

    ├ 测试数据 07：答案正确... (161ms, 972KB)

    ├ 测试数据 08：答案正确... (243ms, 972KB)

    ├ 测试数据 09：答案正确... (192ms, 972KB)

    ├ 测试数据 10：答案正确... (321ms, 972KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 1328ms / 972KB

    既不用筛法，也不用压位，短短几行，全部OK

  • 0
    @ 2009-11-06 16:00:15

    AC的内牛满面。。

  • 0
    @ 2009-10-18 15:55:55

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    看到sunny我当时心里一寒。。。

    结果一次A了

    我这次压5位。。。

  • 0
    @ 2009-10-18 11:19:55

    Accepted 有效得分：100 有效耗时：0ms

    .....怎么感觉算组合数乘法的题目vijos上好多额。。有点重题的感觉。。。。

  • 0
    @ 2009-10-07 08:07:02

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    筛素+分解质因数+高精 + vivid puppy = 秒杀

    注意公式为c（n+m,m）

  • 0
    @ 2009-09-07 23:49:01

    难度4？…………

    筛法（或者素数表）+分解质因数+高精度乘

    懒得优化到0ms了。

  • 0
    @ 2009-08-19 17:47:55

    Accepted 有效得分：100 有效耗时：725ms

    我喜欢筛法~~可是我编的程序和各位大牛筛法相比貌似有点慢啊.......

  • 0
    @ 2009-07-29 22:25:07

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 41ms

    ├ 测试数据 09：答案正确... 41ms

    ├ 测试数据 10：答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：154ms

    虽然没有0ms，但也还说得过去。

    庆祝188题！！

  • 0
    @ 2009-07-27 14:19:48

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 134ms

    ├ 测试数据 07：答案正确... 1197ms

    ├ 测试数据 08：答案正确... 2134ms

    ├ 测试数据 09：答案正确... 1588ms

    ├ 测试数据 10：答案正确... 2400ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：7453ms

    好险，

    用最贱的方法，居然能过！

  • 0
    @ 2009-07-21 14:39:20

    楼下的用的啥方法啊？

  • 0
    @ 2009-07-19 20:55:22

    编译通过...

    ├ 测试数据 01：答案正确... 181ms

    ├ 测试数据 02：答案正确... 181ms

    ├ 测试数据 03：答案正确... 197ms

    ├ 测试数据 04：答案正确... 150ms

    ├ 测试数据 05：答案正确... 150ms

    ├ 测试数据 06：答案正确... 166ms

    ├ 测试数据 07：答案正确... 447ms

    ├ 测试数据 08：答案正确... 525ms

    ├ 测试数据 09：答案正确... 462ms

    ├ 测试数据 10：答案正确... 509ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：2968ms

    比大家的慢

  • 0
    @ 2009-06-28 09:38:29

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    用筛法，没有特殊考虑0的情况，程序WA了3次。

    0ms不必用快速幂，因为除了前几个小素数，大的素数个数不会太多，快速幂没有效果。关键就是用筛法！

  • 0
    @ 2009-05-16 20:23:03

    难度4.。。。。。。。

    没有1A。。真是遗憾。。

    我发现加了TRUNC还不如不加。。。。

    很诡异

    我在自己机子里走了下50000 50000

    是这样的。。

  • 0
    @ 2009-04-09 23:38:05

    把5w看成5k了..

  • 0
    @ 2009-03-20 18:42:38

    幸好有公式支撑，不然还要用矩阵*

  • 0
    @ 2009-03-28 18:17:11

    JZP大牛,hi!（就是oimaster)

    看了你的题解，一次AC

    不过，

    C(m+n,m）和C（m+n，n)有区别吗

    （还有，ans数组开到100就够了）

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

猩猩散步

信息

ID
1156
难度
6
分类
其他 | 数学 、 高精度 点击显示
标签
递交数
595
已通过
160
通过率
27%
被复制
6
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1