来自"NOCOW"

枚举素数和两个素数的乘积，运用容斥原理判断.

#include <iostream>
 
using namespace std;
 
long long k,s;
long long i,j,l,ans;
 
long long prime (long long x)
{
     long long y;
     for (y=2;y<x;y++)
         if (x%y==0) return (0);
     return (1);
}
 
long long c (long long x,long long y)
{
     long long i,aa=1,bb=2;
     for (i=x-y+1;i<=x;i++)
         {
         aa*=i;
         if ((bb<=y)&&(aa%bb==0)) {
                                  aa=aa/bb;
                                  bb++;
                                  }
         }
     while (bb<=y)
           {
           aa=aa/bb;
           bb++;
           }
     return (aa);
}
 
int main ()
{
    cin>>k>>s;
    for (i=2;i<=s;i++)
        if (prime(i)) {
                      if (i*k<=s) ans+=(c(s/i,k));
                      if (ans>10000) {
                                     ans=10000;
                                     break;
                                     }
                      }
                      else {
                           l=0;
                           for (j=2;j<i;j++)
                               if ((i%j==0)&&(prime(j))&&(prime(i/j))&&(i!=j*j)) {
                                                                                 l=1;
                                                                                 break;
                                                                                 }
                           if (l==0) continue;
                           if (i*k<=s) ans-=(c(s/i,k));
                           if (ans>10000) {
                                          ans=10000;
                                          break;
                                          }
                           }
    cout<<ans<<endl;
    return (0);
}

---

long long c (long long x,long long y)不是必需的，用杨辉三角可以dp出来。

个人觉得好像判断解的数目大于10000的方法可以再深入讨论一下……（我骗分我自豪）--Wecing 16:13 2010年7月15日 (CST)

---

回朔的pascal代码：

program cyd;
  var
    p:array[1..100]of boolean;
    d:array[1..30]of integer;
    i,j,k,l,m,n,a,b,c,t:longint; ans:int64;
  function gcd(a,b:int64):int64;
    var
      c:int64;
    begin
      if a<b then begin c:=a; a:=b; b:=c; end;
      while b<>0 do
        begin
          c:=b;
          b:=a mod b;
          a:=c;
        end;
      exit(a);
    end;
  function fx(n,m:longint):int64;
    var
      i:longint; ans,a,b,x,y,z:int64;
    begin
      if n<m then exit(0);
      if m=n then exit(1);
      if m=1 then exit(n);
      a:=m;
      b:=1;
      x:=1;
      y:=1;
      for i:=1 to n-m-1 do
        begin
          inc(a); inc(b);
          x:=x*a; y:=y*b;
          z:=gcd(x,y);
          x:=x div z;
          y:=y div z;
        end;
      x:=x*n;
      exit(x div y);
    end;
  procedure solve(v,x:longint; gc:int64);
    var
      j:longint;
    begin
      if v>t then
        begin
          if gc=1 then exit;
          j:=n div gc;
          inc(ans,fx(j,k)*x);
          exit;
        end;
      solve(v+1,x,gc);
      gc:=gc*d[v];
      if gc<=n then solve(v+1,0-x,gc);
    end;begin
    readln(k,n);
    i:=2;
    while true do
      begin
        while (p[i])and(i<=n) do inc(i);
        if i=n+1 then break;
        inc(t);
        d[t]:=i;
        j:=i;
        while i+j<=n do
          begin
            p[i+j]:=true;
            j:=j+i;
          end;
        inc(i);
      end;
    solve(1,-1,1);
    if ans<10000 then writeln(ans)
                 else writeln(10000);
  end.