2158. 多-有丝分裂

【题目描述】

有丝分裂图解模型：

上述四个时期分别为有丝分裂的间期，中期，后期和末期

间期：DNA复制，DNA分子加倍

中期：染色体排列在赤道板上，然后分为两条染色单体

后期：染色体在纺锤丝的牵引下移向细胞两极

末期：染色体变成染色质，细胞膜向内凹陷，形成两个子细胞

这样，一个细胞经过有丝分裂后，形成了两个子细胞。

Asm.def在成功刺杀特朗普后，被金正恩总统晋升为了将军，他又接到了一个任务--破坏另一个疯狂分子方教授的绿坝长墙，从而入侵人工智能的控制系统。经过观察发现，方教授的绿坝长墙由大量坚固的有机纤维仿生免疫细胞和一个免疫系统组成，为此，他派生物化学专家Satoshi研究出了一种新的细菌，这种细菌可以入侵纤维细胞，使防御系统瓦解，不仅如此，该细菌繁殖速度快，可以进行多-有丝分裂，一次有丝分裂染色体复制为原来的a倍，移向细胞的a个极，然而绿坝长墙的免疫系统十分强大（虽然只有人工智能模拟人体的第二道防线的吞噬细胞），这种吞噬细胞有无限个，每个吞噬细胞最多可以吞噬c个细菌（吃饱状态），这些吞噬细胞会前赴后继的摄取细菌，如果最后一个吞噬细胞吃不饱，并且刚好吃了b个(0<b<c,小于b个该吞噬细胞会感叹：这就是命！大于b个该吞噬细胞就不会觉得不公平)，若刚好等于b个该免疫细胞就会感到不公平(种族歧视，性别歧视，同性恋歧视，各种歧视)，则免疫系统会爆发内战和共产主义革命从而崩溃。

Asm.def挠了挠头，想出了一个极好的点子，使细菌大量繁殖T代，然后恰好让最后一个吞噬细胞感到社会的黑暗面！

细菌处于理想种群的“J”型增长（不受环境控制），由于该细菌十分珍贵，我们只有一个细菌且为了节省蛋白质，我们要让细菌繁殖代数尽量少，你的任务就是求出最少需要繁殖多少代。

细菌至少需要繁殖一代

【输入格式】

第一行一个正整数n,表示数据组数

第2-n+1行每行三个正整数a,b,c

【输出格式】

共n行，若T存在,输出T

否则输出no solution

【样例输入】

4
4 6 10
2 1 2
2 1 7
2 1 4

【样例输出】

2
no solution
3
no solution

【提示】

样例解释：第一组数据：细菌第一次繁殖1->4,第二次繁殖4->16,第一个吞噬细胞吃掉10个细菌，第二个吞噬细胞恰好吃掉6个，然后恰好崩溃需要繁殖两代

第二组数据：无论如何繁殖都不可能剩下一个，所以无解

第三组数据:细菌第一次繁殖1->2,第二次繁殖2->4,第三次繁殖4->8,第一个吞噬细胞吃掉7个细菌，第二个恰好吃掉一个1个，需要繁殖3代

第四组数据：当细菌不繁殖时满足，即T=0，但是题目要求T>=1

为欧拉函数,表示1~n-1与n互质的数的个数, a,b互质的定义：gcd(a,b)=1

夹心数n:=n-1

费马-欧拉定理:

乘法逆元:,最小正整数x称为a mod b的乘法逆元，乘法逆元可以通过扩展欧几里得算法求得

如果(a^d)^k mod c =1,则(a^d) mod c=1

数据范围：

对于20%的数据，ans<=100

对于另外10%的数据，b=1,c为夹心数

对于另外20%的数据，b=1

对于另外20%的数据，c为夹心数

对于100%的数据，0<=a,b<2^31，c<=1000000007,答案保证在64位整数以内

关于细菌的“J”型增长模型:为指数增长，2-有丝分裂的增长模型为2^T,多-有丝分裂的增长模型请自行推导

【来源】

生物《必修3》第四章种群与群落 

ZLXSC2015