首页 > 代码库 > 【模拟】 兔农
【模拟】 兔农
免农 CH Round #54 - Streaming #5 (NOIP模拟赛Day1)
描述
(如果你想更好地理解本题,请先阅读NOI2011第一试“兔农”一题)
萌蛋近年收入不景气,正在她发愁如何能多赚点钱时,她听到隔壁的小朋友在讨论免子繁殖的问题。(注:免子是一种简单的单细胞生物)
问题是这样的:时刻0有2只刚出生的免子。每一时刻,每只免子都会分裂成为2只免子。问时刻n共有多少只免子?
聪明的你可能已经发现,时刻n的免子数正好是第n+1个2的幂次。萌蛋不懂什么叫幂,但她也发现了规律:时刻n+1的免子数等于时刻n的免子数的2倍。前几个时刻(从0开始)的免子数依次为:
2 4 8 16 32 64 128 256 512 …
萌蛋发现越到后面免子数增长的越快,期待养免子一定能赚大钱,于是萌蛋在时刻0买了2只免子开始培养。
每天,萌蛋都要给免子们提供营养。免子的培养基非常特别,每k只免子占据一个培养基,最后剩下的不足k只占据一个培养基。由于免子特别害怕孤独,如果某个培养基只有1只免子,这只免子就会很快死掉。
然而,每个时刻的免子数仍然是可以计算的。例如,当k=7时,前几个时刻(从0开始)的免子数依次为:
2 4 7 14 28 56 112 224 448 …
给定n,你能帮助萌蛋计算时刻n她有多少只免子么?由于答案可能非常大,你只需要告诉萌蛋时刻n的免子只数对p的余数即可。
输入格式
输入只有一行,包含三个整数n k p。
输出格式
输出只有一行,为一个整数,表示时刻n的免子只数对p的余数。
样例输入
6 7 10086
样例输出
112
数据范围与约定
对于30%的数据,n≤1,000,000。
另有30%的数据,k是p的正整数倍。
对于100%的数据,n≤1,000,000,000,2≤k≤1,000,000,1≤p≤1,000,000。
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<string>#include<cmath>#include<algorithm>#include<queue>#include<vector>#include<set>using namespace std;#define INF 1<<30#define LL long longLL n,k,p;LL pow(LL x){ LL ans=1,y=2; while(x) { if(x&1) ans=ans*y%p; y=(y*y)%p; x=x>>1; } return ans%p;}int main(){ scanf("%I64d%I64d%I64d",&n,&k,&p); LL ans=2,tem=2; if(k%2==0) { printf("%I64d\n",2*pow(n)); return 0; } for(int i=1;i<=n;i++) { tem=(tem*2)%k; if(tem%k==1) { printf("%I64d\n",(ans*2-1)*pow(n-i)%p); return 0; } ans=(ans*2)%p; } printf("%I64d\n",ans); return 0;}
【模拟】 兔农
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。