HDU4675[GCD of scequence][組合數學、費馬小定理、取模]

知識1：

費馬小定理是數論中的一個重要定理，其內容為：假如p是質數，且(a,p)=1，那麼 a^(p-1) ≡1（mod p）假如p是質數，且a,p互質，那麼 a的(p-1)次方除以p的余數恆等於1

對於除法取模還需要用到費馬小定理： a ^ (p - 1) % p = 1; -> a ^ (p - 2) % p = (1 / a) % p;

巧妙1：

for(int i=1;i<=n;i++)

{ int temp; scanf("%d",&temp); sum1[temp]++; }

for(int j=i;j<=m;j+=i) sum+=sum1[j];

直接判斷倍數是否有無。ORZ!!!

用這一塊代碼，這樣再從1遍歷到m的時候，速度增加非常快，然後就不會超時。

#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <cstring>   
#include <cmath>   
#include <ctime>   
#include <iostream>   
#include <algorithm>   
#include <string>   
#include <queue>   
#include <set>   
#include <map>   
#include <vector>   
#include <assert.h>   
  
using namespace std;  
  
#define lowbit(i) (i&-i)   
#define sqr(x) ((x)*(x))   
#define enter printf("\n")   
#define is_sqr(x) (x&(x-1))   
#define pi acos(-1.0)   
#define clr(x)  memset(x,0,sizeof(x))   
#define fp1 freopen("in.txt","r",stdin)   
#define fp2 freopen("out.txt","w",stdout)   
#define pb push_back   
  
typedef __int64 LL;  
  
const double eps = 1e-7;  
const double DINF = 1e100;  
const int INF = 1000000006;  
const LL LINF = 1000000000000000005ll;  
const int MOD = (int) 1e9 + 7;  
const int maxn=300005;  
  
 template<class T> inline T Min(T a,T b){return a<b?a:b;}  
 template<class T> inline T Max(T a,T b){return a>b?a:b;}  
 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}  
 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}  
  
  
LL f[maxn],e[maxn],a[maxn],ans[maxn],sum1[maxn];  
LL quick_pow(LL a,LL b)//a的b次方,快速冪取模   
{  
    LL ret=1;  
    while(b)  
    {  
        if(b&1) ret=(ret*a)%MOD;  
        b/=2;  
        a=(a*a)%MOD;  
    }  
    return ret%MOD;  
}  
LL cal(LL n,LL k)  
{  
    if(k==0||n==k) return 1;  
    return (f[n]*e[k]%MOD)*e[n-k]%MOD;//注意運算順序   
}  
  
//以後某些變量還是不采用C99的寫法了   
int main()  
{  
  f[0]=e[0]=1;  
  for(int i=1;i<=maxn;i++)  
  {  
      f[i]=f[i-1]*i%MOD;  
      e[i]=quick_pow(f[i],MOD-2);  
  }  
  int n,m,k;  
  while(scanf("%d%d%d",&n,&m,&k)!=EOF)  
  {  
      clr(sum1);  
      for(int i=1;i<=n;i++)  
      {  
         int temp;  
         scanf("%d",&temp);  
         sum1[temp]++;  
      }  
      for(int i=m;i>=1;i--)//倒著寫不至於每次都m/i次循環   
      {  
          int sum=0;  
          for(int j=i;j<=m;j+=i)  
            sum+=sum1[j];  
          if(sum<n-k)//k個不一樣的，n-k個一樣的。   
          {  
              ans[i]=0;continue;  
          }  
          ans[i]=((cal(sum,n-k)*quick_pow(m/i-1,sum-(n-k))%MOD)*quick_pow(m/i,n-sum))%MOD;  
          for(int j=2*i;j<=m;j+=i)  
              ans[i]=(ans[i]-ans[j]+MOD)%MOD;  
      }  
      for(int i=1;i<m;i++) printf("%lld ",ans[i]);  
      printf("%lld\n",ans[m]);  
  }  
  return 0;  
}  

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>

using namespace std;

#define lowbit(i) (i&-i)
#define sqr(x) ((x)*(x))
#define enter printf("\n")
#define is_sqr(x) (x&(x-1))
#define pi acos(-1.0)
#define clr(x)  memset(x,0,sizeof(x))
#define fp1 freopen("in.txt","r",stdin)
#define fp2 freopen("out.txt","w",stdout)
#define pb push_back

typedef __int64 LL;

const double eps = 1e-7;
const double DINF = 1e100;
const int INF = 1000000006;
const LL LINF = 1000000000000000005ll;
const int MOD = (int) 1e9 + 7;
const int maxn=300005;

 template<class T> inline T Min(T a,T b){return a<b?a:b;}
 template<class T> inline T Max(T a,T b){return a>b?a:b;}
 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}


LL f[maxn],e[maxn],a[maxn],ans[maxn],sum1[maxn];
LL quick_pow(LL a,LL b)//a的b次方,快速冪取模
{
    LL ret=1;
    while(b)
    {
        if(b&1) ret=(ret*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ret%MOD;
}
LL cal(LL n,LL k)
{
    if(k==0||n==k) return 1;
    return (f[n]*e[k]%MOD)*e[n-k]%MOD;//注意運算順序
}

//以後某些變量還是不采用C99的寫法了
int main()
{
  f[0]=e[0]=1;
  for(int i=1;i<=maxn;i++)
  {
      f[i]=f[i-1]*i%MOD;
      e[i]=quick_pow(f[i],MOD-2);
  }
  int n,m,k;
  while(scanf("%d%d%d",&n,&m,&k)!=EOF)
  {
      clr(sum1);
      for(int i=1;i<=n;i++)
      {
         int temp;
         scanf("%d",&temp);
         sum1[temp]++;
      }
      for(int i=m;i>=1;i--)//倒著寫不至於每次都m/i次循環
      {
          int sum=0;
          for(int j=i;j<=m;j+=i)
            sum+=sum1[j];
          if(sum<n-k)//k個不一樣的，n-k個一樣的。
          {
              ans[i]=0;continue;
          }
          ans[i]=((cal(sum,n-k)*quick_pow(m/i-1,sum-(n-k))%MOD)*quick_pow(m/i,n-sum))%MOD;
          for(int j=2*i;j<=m;j+=i)
              ans[i]=(ans[i]-ans[j]+MOD)%MOD;
      }
      for(int i=1;i<m;i++) printf("%lld ",ans[i]);
      printf("%lld\n",ans[m]);
  }
  return 0;
}