质因数分解
注意改变指数的时候要判断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;
}
```

#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;
}

/*
一个很简单的数论问题了~~
做法很简单
首先我们筛出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();
}
     

就是个分数约分水题，先筛素数，然后分解分母和分子，对于每个素数，如果分子出现次数>分母出现次数（出现次数指的是分解质因数得到此数的此数），则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;
}


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.

貌似没有什么必要打素数表。
\( 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;
}

首先预处理出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;
}

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

#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;

}
}

}

###悲剧了

记录信息
评测状态 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_);
}

#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;
}

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

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

这只有难度一吧

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

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

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.

编译通过...

├ 测试数据 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.

怎么都遇不到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次

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

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

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

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

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

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

终于ms了，puppy无敌