题目描述:
艾星人和喵星人开战了!
但是CWY发现,这只是大宇宙意志的一场“阴谋”,旨在控制艾星和喵星的人口数量。
战争最后的结果无非就是两败俱伤,人口锐减。
但是CWY想知道是艾星和喵星的人口总数是多少,以此预知战争的伤亡情况。
艾星和喵星人口总数为n,分别标号1到n,其中艾星人的标号是1到n中属于给定的等差数列或等比数列的数字。
给定等差数列的首项a,公差b,等比数列的首项c,公比d,你的任务是求出艾星人的个数。
输入格式:
一行,5个整数,分别是a,b,c,d,n。
(1≤a,b,c,n≤1012, 1≤d≤105。)
对于80%的数据,1≤n≤1000000。
输出格式:
一个整数,表示艾星人个数。
输入输出样例:
输入样例 |
1 1 1 2 1000 |
3 3 1 2 1000 |
452 24 4 5 600 |
输出样例 |
1000 |
343 |
10 |
样例解释 |
产生的等差数列是:1,2,3,4,…. 产生的等比数列是:1,2,4,8,…. 所以【1,1000】范围内所有标号都是艾星人的。 |
|
艾星人的10个数分别是: 4,20,100,452,476,500,524,548,572,596 |
今天不知道为什么调试器暴走……
而且把a>n的特判给打反
这题就是先算出等比的,再算等差(指数函数很快,记得用int64) ,再特判
Program queue; var a,b,c,d,n,ans,i,ii:int64; function is_ok:boolean; begin if (a>n) then exit(false); if (c-a>=0) then if ((c-a) mod b=0) then if ((c-a) div b>=-1) then exit(true); exit(false); end; begin assign(input,'queue.in'); assign(output,'queue.out'); reset(input); rewrite(output); read(a,b,c,d,n); if (a>n) then ans:=0 else ans:=(n-a) div b+1; while (c<=n) do begin if (not(is_ok) ) then inc(ans); c:=c*d; if (d=1) then break; end; writeln(ans); close(input); close(output); end.