Arab Collegiate Programming Contest 2012 J- Math Homework

思路：由于只有1-6这几个数，而这几个数的最小公倍数是60，所以只需要求出60以内有多少满足条件的数即可。

再就是求出对于给定的n，求出60的倍数。然后就是怎样求的问题了。

首先可以写成如下形式：

               10-40=60*n (把最后的40个数去掉，最后在求结果的时候再加上)

               n=(10-40)/60. (结果一定可以整除)

代码如下：

 #include<cstdio>

 #define ll long long

 #define mod 1000000007

 ll pw(ll a,ll b)

 {

     ll ans=;

     while(b){

         if(b&) ans=ans*a%mod;

         b>>=;

         a=a*a%mod;

     }

     return ans;

 }

 int main()

 {

     int i,j,t;

     ll n;

     char str[];

     bool f[];

     scanf("%d",&t);

     while(t--){

         scanf("%I64d %s",&n,str);

         for(i=;i<;i++){

             f[i]=;

             for(j=;j<;j++){

                 if(str[j]==''&&i%(j+)==) f[i]=;

                 else if(str[j]==''&&i%(j+)!=) f[i]=;

             }

         }

         int c=;

         if(n==){

             for(i=;i<=;i++) c+=f[i];

             printf("%d\n",c);

             continue;

         }

         for(i=;i<;i++) c+=f[i];

         ll p=pw(,n);

         ll ans=(p-+mod)%mod*pw(,mod-)%mod;

         ans=ans*c%mod;

         for(i=;i<;i++) ans+=f[i];

         printf("%I64d\n",ans);

     }

     return ;

 }