题解

75 条题解

  • 1
    @ 2018-08-08 13:22:48

    质因数分解
    注意改变指数的时候要判断x>1
    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;

    int n,m;
    int ex[N];
    void work(int x,int v) {
    if (x<1) return;
    REP(i,2,(int)sqrt(x)) {
    if (x==1) break;
    while (x%i==0) {
    x/=i;
    ex[i]+=v;
    }
    }
    if (x>1) ex[x]+=v;
    }
    int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,n) work(i,1);
    FOR(i,m) work(i,-1);
    FOR(i,n-m) work(i,-1);
    int ans=0;
    FOR(i,n) if (ex[i]) {
    ++ans;
    //cout<<i<<endl;
    }
    cout<<ans<<endl;
    return 0;
    }
    ```

  • 1
    @ 2017-11-21 21:36:31
    #include <iostream>
    #include<cstdlib>
    #include<cstdio>
    #include<map>
    #include<vector>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define mod 7654321
    #define FOR(i,x,y) for(i=x;i<=y;++i)
    #define maxa 10000+100
    #define N 100000+5
    using namespace std;
    int a[N],ans =0;
    map<int,int >p,q;
    vector<int > v;
    void do1(int x,map<int,int > &mm)
    {
        int i;
        for(i=0;i<v.size()&&v[i]<=x;++i)
        {
            if(a[x]==0)
            {
               if(mm.count(x)==0)
                    mm[x] = 1;
                else
                    mm[x]++;
                    return ;
            }
            if(x%v[i]==0)
            {
                while(x%v[i]==0){
                if(mm.count(v[i])==0)
                    mm[v[i]] = 1;
                else
                    mm[v[i]]++;
                    x/=v[i];
                }
            }
        }
    }
    int main()
    {
        int n,m,i,j;
        cin>>n>>m;
        a[1] = 1;
        for(i=2;i<=sqrt(N);++i)
        {
            if(a[i]==0)
            {
                for(j=2;j*i<=N;++j)
                    a[i*j] = 1;
            }
        }
        FOR(i,1,N)
        if(!a[i])
        {
            v.push_back(i);
        }
        for(i=2;i<=m;++i)
            do1(i,p);
          /*  cout<<p.size()<<endl;
       cout<<"hhah"<<endl;
        map<int,int>::iterator it1;
        for(it1 = p.begin();it1!=p.end();++it1)
            cout<<it1->first<<" "<<it1->second<<endl;
     cout<<"hhah"<<endl;*/
    
      for(i=n-m+1;i<=n;++i)
            do1(i,q);
    
     /*map<int,int>::iterator it2;
        for(it2 = q.begin();it2!=q.end();++it2)
            cout<<it2->first<<" "<<it2->second<<endl;*/
    
    
         //   cout<<q.size()<<endl;
        map<int,int>::iterator it;
        int t = 0;
        for(it=q.begin();it!=q.end();++it)
            if(p.count(it->first)==0||p[it->first]<it->second){
                t++;
               // cout<<it->first<<" "<<t<<endl;
            }
            cout<<t<<endl;
    }
    
    
    
  • 1
    @ 2017-05-08 09:04:52
    /*
    一个很简单的数论问题了~~
    做法很简单
    首先我们筛出100000以内的素数表
    大概有9000多个~可以先试验~
    这样我们对于分子分母所有的乘数都拆分成若干个质数乘积
    每次除干净就好了~
    这样我们用一个cnt[i]表示第i个素数还剩多少个~
    分子除素数的时候应该cnt[i]++
    分母除素数的时候应该cnt[i]--
    这样剩下的素数就是要求的了~~
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    
    const int MAXN=100005;
    int vis[MAXN];
    int p[MAXN/10],cnt[MAXN/10];
    int n,m,l;
    int ans;
    
    void init()
    {
        scanf("%d%d",&n,&m);
    }
    
    void Prime()
    {
        int m=sqrt(MAXN+0.5);
        for(int i=2;i<=m;i++)
            if(!vis[i])
                for(int j=i*i;j<=MAXN;j+=i)
                    vis[j]=1;
        for(int i=2;i<MAXN;i++)
            if(!vis[i])
                p[++l]=i;
    }
    
    void mul(int x)
    {
        for(int i=1;i<=9593 && x!=1;i++)
            while(x%p[i]==0) 
                cnt[i]++,x/=p[i];
    }
    
    void chu(int x)
    {
        for(int i=1;i<=9593 && x!=1;i++)
            while(x%p[i]==0) 
                cnt[i]--,x/=p[i];
    }
    
    void work()
    {
        for(int i=n;i>=n-m+1;i--)
            mul(i);
        for(int i=m;i>=1;i--)
            chu(i);
        for(int i=1;i<=9593;i++) 
            if(cnt[i]) 
                ans++;
        cout<<ans<<endl;
    }
    
    int main()
    {
        init();
        Prime();
        work();
    }
         
    
  • 0
    @ 2016-09-16 17:14:45

    就是个分数约分水题,先筛素数,然后分解分母和分子,对于每个素数,如果分子出现次数>分母出现次数(出现次数指的是分解质因数得到此数的此数),则ans++;

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 556 KiB, score = 20

    测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 20

    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 20

    测试数据 #3: Accepted, time = 0 ms, mem = 588 KiB, score = 20

    测试数据 #4: Accepted, time = 0 ms, mem = 836 KiB, score = 20

    Accepted, time = 0 ms, mem = 836 KiB, score = 100
    代码
    c++
    #include <iostream>
    #include <vector>
    using namespace std;
    int main()
    {
    ios::sync_with_stdio(0);
    int n,m,ans=0;cin>>n>>m;
    vector<int> p,nc,to_p(n+1);vector<bool> not_p(n+1);
    for(int i=2;i<=n;i++)
    {
    if(!not_p[i]){to_p[i]=p.size();p.push_back(i);}
    for(int j=0;j<(int)p.size()&&i*p[j]<=n;j++)
    {
    not_p[i*p[j]]=1;
    to_p[i*p[j]]=j;
    if(i%p[j]==0)break;
    }
    }
    nc.resize(p.size());
    for(int i=n;i>m;i--)
    {
    int b=i;
    while(b>1){if(!nc[to_p[b]])ans++;nc[to_p[b]]++;b/=p[to_p[b]];}
    }
    for(int i=n-m;i>1;i--)
    {
    int b=i;
    while(b>1)
    {nc[to_p[b]]--;if(!nc[to_p[b]])ans--;b/=p[to_p[b]];}
    }
    cout<<ans;
    return 0;
    }

  • 0
    @ 2016-04-04 11:11:03

    var
    a,b,o:array [0..200005] of longint;
    n,m,i,j,ans:longint;
    begin
    read(n,m);
    for i:=2 to n do
    begin
    if (o[i]=0) then
    begin o[i]:=i; inc(b[0]); b[b[0]]:=i; end;
    for j:=1 to b[0] do
    if (b[j]<=o[i]) and (i*b[j]<=n)
    then o[i*b[j]]:=b[j] else break;
    end;
    for i:=n-m+1 to n do
    begin
    j:=i;
    while j<>1 do begin inc(a[o[j]]); j:=j div o[j]; end;
    end;
    for i:=2 to m do
    begin
    j:=i;
    while j<>1 do begin dec(a[o[j]]); j:=j div o[j]; end;
    end;
    ans:=0;
    for i:=1 to 100000 do if (a[i]<>0) then inc(ans);
    writeln(ans);
    end.

  • 0
    @ 2016-04-02 22:56:52

    貌似没有什么必要打素数表。
    \( C_n^m = \frac{n!}{m!(n-m)!} = \frac{(m+1)\cdots n}{1\cdots (n-m)}\qquad\)
    不妨开一个数组 num[1...n],num[i] 记录质因数 i 出现的次数。详见代码。

    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    int num[500000];
    int main(){
    int n, m, i, j, k;
    int rst = 0;
    memset(num, 0, sizeof num);
    scanf("%d %d", &n, &m);
    for(i=2; i<=n-m; i++){ //第一步:对分母分解质因数
    for(j=i, k=2; k<=j && j>0; ){
    while(j%k == 0){
    j /= k;
    num[k]--;
    }
    k++;
    }
    }
    for(i=m+1; i<=n; i++){ //第二步:对分子分解质因数
    for(j=i, k=2; k<=j && j>0; ){
    while(j%k == 0){
    j /= k;
    num[k]++;
    }
    k++;
    }
    }
    for(i=2; i<=n; i++){ //第三步:统计质数个数
    if(num[i] > 0){
    for(j=2; j<=sqrt(i); j++){
    if(i%j == 0)
    break;
    }
    if(j > sqrt(i))
    rst++;
    }
    }
    printf("%d", rst);
    return 0;
    }

  • 0
    @ 2015-10-28 19:42:32

    首先预处理出2到100000的所有质数 筛法很快就可以求出来,总共有9593个。
    然后对于每一个数 将其因式分解 然后记录一下每个质数的次数 乘的时候+,除的时候减,然后扫一遍质数次数的数组就可以求出来了

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int N=100010;
    bool vis[N];
    int tot,p[11000],num[11000],n,m,ans;

    void mul(int x){
    for(int i=1;i<=9593 && x!=1;i++)
    while(x%p[i]==0) num[i]++,x/=p[i];
    }

    void chu(int x){
    for(int i=1;i<=9593 && x!=1;i++)
    while(x%p[i]==0) num[i]--,x/=p[i];
    }
    int main(){
    for(int i=2;i<=N;i++){
    if(!vis[i]) p[++tot]=i;
    for(int j=1;i*j<=N;j++) vis[i*j]=true;
    }
    scanf("%d%d",&n,&m);
    for(int i=n;i>=n-m+1;i--) mul(i);
    for(int i=1;i<=m;i++) chu(i);
    for(int i=1;i<=9593;i++) if(num[i]) ans++;
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2015-10-10 14:45:53

    尼玛这是考数学啊!!!!!!!

    #include<stdio.h>
    int fun1(int a);
    int fun2(int a);
    int L1[100010][3];

    int main()
    {
    int m,n,a,b,i,p;
    p=0;
    for (a=0;a<=100010;a++)
    for (b=0;b<=3;b++)

    L1[a][b]=0;

    scanf("%d %d",&n,&m);

    for (i=n-m+1;i<=n;i++)
    fun1(i);
    for (i=2;i<=m;i++)
    fun2(i);

    for (i=2;i<=100009;i++)
    {
    if(L1[i][1]>L1[i][2]) p++;
    }

    printf("%d",p);

    }

    int fun1(int a)
    {
    int m,n,i,b,j;
    for (i=2;i<=a;i++)
    {
    if (a%i==0)
    {
    L1[i][1]=L1[i][1]+1;
    a=a/i;
    //printf("%d ",i);
    i=1;

    }
    }

    }

    int fun2(int a)
    {
    int m,n,i,b,j;
    for (i=2;i<=a;i++)
    {
    if (a%i==0)
    {
    L1[i][2]=L1[i][2]+1;
    a=a/i;
    //printf("%d ",i);
    i=1;

    }
    }

    }

  • 0
    @ 2015-08-15 20:27:41

    ###悲剧了

    记录信息
    评测状态 Time Limit Exceeded
    题目 P1137 组合数
    递交时间 2015-08-15 20:24:04
    代码语言 C++
    评测机 VijosEx
    消耗时间 1077 ms
    消耗内存 908 KiB
    评测时间 2015-08-15 20:24:06
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 1 ms, mem = 908 KiB, score = 20
    测试数据 #1: Accepted, time = 15 ms, mem = 908 KiB, score = 20
    测试数据 #2: Accepted, time = 15 ms, mem = 904 KiB, score = 20
    测试数据 #3: Accepted, time = 31 ms, mem = 908 KiB, score = 20
    测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 896 KiB, score = 0
    TimeLimitExceeded, time = 1077 ms, mem = 908 KiB, score = 80
    代码
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int ans[100100];
    int main()
    {
    int n,k;
    scanf("%d%d",&n,&k);
    int l=max(k,n-k);
    for(int i=l+1;i<=n;i++)
    {
    int a=i;
    for(int j=2;;)
    {
    if(a==1)break;
    if(a%j==0)
    {
    a/=j;
    ans[j]++;
    }
    else j++;
    }
    }
    int lo=min(k,n-k);
    for(int i=2;i<=lo;i++)
    {
    int a=i;
    for(int j=2;;)
    {
    if(a==1)break;
    if(a%j==0)
    {
    ans[j]--;
    a/=j;
    }
    else j++;
    }
    }
    int a=0;
    for(int i=2;i<=n;i++)
    if(ans[i]!=0)a++;
    printf("%d",a);
    }
    ###AC了

    1137组合数Accepted
    记录信息
    评测状态 Accepted
    题目 P1137 组合数
    递交时间 2015-08-15 20:46:59
    代码语言 C++
    评测机 VijosEx
    消耗时间 189 ms
    消耗内存 4932 KiB
    评测时间 2015-08-15 20:47:00
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 2 ms, mem = 4924 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 4924 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 4932 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 4924 KiB, score = 20
    测试数据 #4: Accepted, time = 187 ms, mem = 4924 KiB, score = 20
    Accepted, time = 189 ms, mem = 4932 KiB, score = 100

    代码
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int prime[100101]={1,2,3,5,7,11};
    bool num[100101]={0,0,0,0,1,0};
    int ans[1001000];
    int main()
    {
    int now=1;
    for(int i=2;i<100001;i++)
    {
    if(num[i]==false)
    prime[now++]=i;
    for(int j=1;prime[j]*i<=100000;j++)
    {
    num[i*prime[j]]=true;
    if(i%prime[j]==0)
    break;
    }
    }
    int n,k,ans_=0;
    scanf("%d%d",&n,&k);
    int l=max(k,n-k);
    for(int i=l+1;i<=n;i++)
    {
    int a=i;
    for(int j=1;;)
    {
    if(a==1)break;
    if(a%prime[j]==0)
    {
    a/=prime[j];
    ans[prime[j]]++;
    if(ans[prime[j]]==1)
    ans_+=1;
    }
    else j+=1;
    }
    }
    int lo=min(k,n-k);
    for(int i=2;i<=lo;i++)
    {
    int a=i;
    for(int j=1;;)
    {
    if(a==1)break;
    if(a%prime[j]==0)
    {
    ans[prime[j]]--;
    a/=prime[j];
    if(ans[prime[j]]==0)
    ans_-=1;
    }
    else j++;
    }
    }
    printf("%d",ans_);
    }

  • 0
    @ 2015-03-16 16:31:53

    #include<iostream>
    #include<string>
    #include<string.h>
    #include<math.h>
    #include<stdlib.h>
    using namespace std;
    int prime[10000];
    int primeSize = 0;
    int cnt[100001];
    void init(){
    bool a[100001];
    memset(a, -1, sizeof(a));
    for (int i = 2; i < 100000; i++){
    if (a[i])
    prime[primeSize++] = i;
    for (int j = 0; j < primeSize&&prime[j] * i < 100000; j++){
    a[prime[j] * i] = false;
    if (i%prime[j] == 0)break;
    }
    }
    }
    int main(){
    freopen("in.txt", "r", stdin);

    init();
    long long int n, m;
    cin >> n >> m;
    if ((m << 1) > n)m = n - m;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < m; i++){
    int num = n - i;
    for (int j = 0; j < 67; j++){
    while (num%prime[j] == 0){
    num /= prime[j];
    cnt[prime[j]]++;
    }
    }
    if (num != 1)cnt[num]++;
    }
    for (int i = 2; i <= m; i++){
    int num = i;
    for (int j = 0; j < 67; j++){
    while (num%prime[j] == 0){
    num /= prime[j];
    cnt[prime[j]]--;
    }
    }
    if (num != 1)cnt[num]--;
    }
    int ans = 0;
    for (int i = 0; i < primeSize; i++){
    if (cnt[prime[i]])ans++;
    }
    cout << ans << endl;
    return 0;
    }

  • 0
    @ 2014-07-09 17:05:01

    真心希望每个出题的人能给出测试数据的范围。这样考该数据范围过得日子也就oj上有,真是比赛时不会有的
    基本思路c=m+1*...*n/(1*...*n-m)
    所以,首先获取质数表,然后对每一个因数分解质因数(不要先乘出来,否则可能会爆),分解质因数时只需要保存与对应质数表中的质数的质数即可(我分别保存在num1和num2)
    然后进行约分时,只需用num1的每一项减去num2中的即可。剩下的不提示了
    数据范围提示,经过我改范围,然后由过到不过来看,质因数最大不会超过60000

  • 0
    @ 2013-10-17 19:59:28

    vj的题目等级真高,连数据范围都没有。。
    姑且当他不会超时把
    首先打一个素数表。
    然后把C(n,r)中r,n都分解素数,对应的素数num存在f,g数组里
    然后扫一遍素数表,把g[i]-f[i]累加一边就是答案了。
    注意细节。
    DXE-syf
    2013-10-17

  • 0
    @ 2012-08-09 21:49:51

    这只有难度一吧

  • 0
    @ 2009-11-10 16:05:36

    。。。原来这里还藏着道水题。。。

  • 0
    @ 2009-11-02 16:14:30

    组合数性质,数学讲过的。。。

  • 0
    @ 2009-10-31 16:49:40

    Program Vijos_P1137;

    Var

    i, j, m, n, s: dWord;

    v: Array [2..50000] Of Boolean;

    Function Calc(n: dWord): Word;

    Begin

    Calc:=0;

    While n>1 Do

    Begin Inc(Calc, n Div i); n:=n Div i End

    End;

    Begin

    Read(n, m); FillChar(v, n, True); s:=0;

    For i:=2 To n Do

    If v[i] Then Begin

    j:=i Shl 1;

    While jCalc(m)+Calc(n-m)) Then Inc(s);

    WriteLn(s)

    End.

  • 0
    @ 2009-10-25 17:38:26

    编译通过...

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

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

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

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

    ├ 测试数据 05:运行超时...

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

    Unaccepted 有效得分:80 有效耗时:0ms

    var

    ans,i,j,t,n,m,tt:longint;

    a,d:array[0..10000] of longint;

    prime:boolean;

    procedure fen(n,code:longint);

    var

    i:longint;

    begin

    for i:=1 to tt do begin

    if d[i]>n then break;

    while (n mod d[i]=0)and(n>0) do begin

    inc(a[i],code);

    n:=n div d[i];

    end;

    end;

    end;

    begin

    readln(n,m);

    for i:=2 to n do

    begin

    prime:=true;

    for j:=2 to trunc(sqrt(i)) do

    if i mod j=0 then begin

    prime:=true;break;

    end;

    if prime then begin

    inc(tt);

    d[tt]:=i;

    end;

    end;

    t:=m;

    if n-m>t then t:=n-m;

    for i:=n downto t+1 do

    fen(i,1);

    for i:=t downto 1 do

    fen(i,-1);

    for i:=1 to tt do

    if a[i]>0 then inc(ans);

    writeln(ans);

    end.

  • 0
    @ 2009-10-24 20:42:57

    怎么都遇不到puppy,用我写的ws普通素数表怎么都超时,于是改了一下算法,弱弱地秒杀了

    编译通过...

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

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

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

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

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

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

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

    建立素数表,对于每个素数判断是否因数

    对于每个因数,首先算出n!中该素数的指数a,再算出m!中该素数的指数b,最后算出(n-m)!中该素数的指数c,判断a-b-c是否等于0即可

    计算k!中素数t的指数ans的算法:[code]ans=0;

    while(k)

    {

    k/=t;

    ans+=k;

    }

    [/code]

    这个算法对于数据:50000 25000 约循环100000次

  • 0
    @ 2009-10-18 10:25:39

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

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

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

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

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

    整体分解阶乘。。。。直接一次AC

  • 0
    @ 2009-10-10 07:20:16

    终于ms了,puppy无敌

信息

ID
1137
难度
5
分类
组合数学 | 其他 | 数学 点击显示
标签
(无)
递交数
1243
已通过
406
通过率
33%
上传者