[PA2015]Hazard
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 69 Solved: 19
[Submit][Status][Discuss]
Description
有n个人在轮流玩赌博机，一开始编号为i的人有a[i]元钱。赌博机可以抽象为一个长度为m的仅包含1和-1的序列，若抽到1，那么你将得到1块钱；若抽到-1，你将输掉1块钱。
第1局，第1个人会抽到序列中的第1项；第2局，第2个人会抽到序列中的第2项；第3局，第3个人会抽到序列中的第3项......即：第i个人抽完后轮到第i+1个人去抽，特别地，第n个人抽完后轮到第1个人去抽。序列第i项被抽到之后，下一个被抽到的将会是第i+1项，特别地，序列第m项被抽到之后，下一个被抽到的将会是第1项。
如果在某一轮，有个人输光了所有的钱，那么这场赌博游戏就会结束，请求出游戏在哪一轮结束，或者判断这个游戏会永远进行下去。
Input
第一行包含一个正整数n(1<=n<=1000000)，表示玩家的个数。
第二行包含n个正整数a[1],a[2],...,a[n](1<=a[i]<=1000000)，依次表示每个玩家一开始持有的钱数。
第一行包含一个正整数m(1<=m<=1000000)，表示序列的长度。
第四行包含一个长度为m的仅包含W和P的字符串，表示这个序列，其中W表示1，P表示-1。
Output
若游戏会永远进行下去，输出-1。否则输出游戏在哪一轮结束。
Sample Input
4
2 3 2 1
3
WPP
2 3 2 1
3
WPP
Sample Output
12
HINT
Source
题解：发现最大的f(n)不会超过9∗9∗18=1458，因此我们枚举f(n)，O(logn)Check即可
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib> #define ll long long
using namespace std;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} ll n,m;
ll k,a,b; ll F (ll x)
{
ll res=;
while(x)
{
res+=(x%)*(x%);
x/=;
}
return res;
}
int main()
{
ll ans=;
k=read(),a=read(),b=read();
for (int i=min(1458ll,b/k);i>=;i--)
{
ll n=i*k;
if (n>=a&&i==F(n)) ans++;
}
printf("%lld\n",ans);
}