首页 > 代码库 > NOIP模拟题——细胞分裂
NOIP模拟题——细胞分裂
【问题描述】
小 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<cstdio> 2 #include<iostream> 3 #include<cstring> 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<cstdio>#include<iostream>#include<cmath>#include<cstring>using namespace std;char s[100005];int x,y;void solve(){ char c; int len=strlen(s); for(int i=0;i<len;i++) { c=s[i]; x=((c-‘0‘)+x*10)%(y-1); }}int main(){ freopen("cell.in","r",stdin); freopen("cell.out","w",stdout); scanf("%s %d",s,&y); solve(); int ans=1; for(int i=1;i<=x;i++) ans=(ans*2)%y; printf("%d",ans);}
NOIP模拟题——细胞分裂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。