【问题描述】

小 A 养了一大坨细胞。 最初小 A 只有 1 个细胞。每秒，小 A 的每个细胞都会分裂成 2 个细胞。

已知：现在离“最初”已经过去了x秒，那么现在的细胞数当然是可以计算的。 小 A 想知道的当然不是当前的细胞数。小 A 知道他养的细胞的习性：每 y 个细胞会聚成一团。经常会有剩下的细胞，那么我们称这些细胞是孤独的。 小 A 想知道的就是孤独的细胞个数。

【输入文件】

输入文件为 cell.in。 输入文件共一行，为两个整数 xy，以空格隔开。

【输出文件】

输出文件为 cell.out。 输出文件共一行，为一个整数，即孤独的细胞个数。

【输入样例】

  3 3

【输出样例】

  2

【数据规模和约定】

对于 10%的数据，x<2^6。

对于 20%的数据，x<2^17。

对于 40%的数据，x<2^64。

对于 70%的数据，x<2^2333。

对于 100%的数据，0≤x<2^233333，y 是 3 到 1000 之间（含两端）的质数。

 

法1(70分)：高精度+快速幂

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int x[300000],y[300000]; 6 int qwe; 7 long long solve(int *x) 8 { 9     if((x[0]==0||x[0]==1)&&x[1]==1)return 2;10     int pre=0;int temp=0;11     bool pd=true;12     if(x[1]/2!=0)temp++;13     if(x[x[0]]%2==0)pd=false;//偶数 14     for(int i=1;i<=x[0];i++)15     {16         int k=pre*10+x[i];17         y[temp++]=k/2;18         pre=k%2;19     }20     if(x[1]/2!=0)y[0]=x[0];else y[0]=x[0]-1;21     for(int i=1;i<=y[0];i++)22     x[i]=y[i];23     x[0]=y[0];24     if(pd==true)//奇数 25     {26         long long b=solve(x)%qwe;27         b=b*b*2%qwe;28         return b;29     }30     else31     {32         long long b=solve(x)%qwe;33         b=b*b%qwe;34         return b;35     }36 }37 int main()38 {39     freopen("cell.in","r",stdin);40     freopen("cell.out","w",stdout);41     int temp=0;42     char c=getchar();43     while(c<'0'||c>'9')c=getchar();44     while(c>='0'&&c<='9')45     {46         x[++temp]=c-'0';47         c=getchar();48     }49     x[0]=temp;50     scanf("%d",&qwe);51     long long ans=solve(x);52     printf("%I64d",ans%qwe);53     return 0;54 }
       
      
     

法2：费马小定理：

 假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;char s[100005];int x,y;void solve(){    char c;    int len=strlen(s);    for(int i=0;i