Description
Dante 最近研究出了一种新的兔子cony,这种兔子是一种雌雄同体的生物,具有超强的繁殖能力,每个月它可以产下a-1个新兔子,但每月只能产一次.在b个月以后Dante实验室已经拥有了一大群兔子,有一次他突发奇想准备给cony们照相,他有无数个长凳,每个长凳上可以站c个cony,而且每个长凳上要站满了所有的cony才能使用下一个长凳,可是Dante的兔子们不可能正好让每个长凳都站满,于是他只好舍弃一些cony,现在你能告诉他最少需要舍弃多少个cony呢?(Dante第一个月只有一只兔子)
Input
多组数据测试,每行输入三个整数 a(1 < a < 1000) b(0 < b < 1000000000) c(0 < c< 1000000)
Output
每行输出一个数,需要舍弃的兔子数
Sample Input
3 4 5
Sample Output
2
View Code
1
#include<stdio.h>
2
int
a,c;
3
int
pows(
int
n)
4
{
5
long
long
flg;
6
int
ans;
7
if
(n==
1
)
8
return
a%c;
9
else
10
{
11
flg=pows(n/
2
)%c;
12
ans=(flg*flg)%c;
13
if
(n%
2
)
14
{
15
ans=(ans*a)%c;
16
}
17
return
ans;
18
}
19
}
20
int
main()
21
{
22
int
b;
23
while
(scanf(
"
%d%d%d
"
,&a,&b,&c)!=EOF)
24
{
25
if
(b==
1
)
26
printf(
"
1\n
"
);
27
else
28
printf(
"
%d\n
"
,pows(b-
1
));
29
}
30
return
0
;
31
}
