Owl Geeks(水题)

Description

The owls have the following equation:

Y = a × x2 + b × x

With a, b, and N given, they decide to put into a set the integer values of Y that are less than or equal to N and that are outputted from the equation from any positive integer x.

With that set of numbers, they come up with the problem of finding the winning digit among them.

The winning digit is a digit from 0 to 9 that will get the maximum number of points. How are points for a digit calculated you may ask? Well, be a bit more patient, I’m going to tell you now.

For each number in the set, if the digit was the most repeated digit or tied with other digits as the most repeated digit in the ith number of set S, then it would get one point from that ith number.

Can you tell the owls what the winning digit is?

Input

The first line of input is T – the number of test cases.

The first line of each test case is a, b, and N (1 ≤ a, b, N ≤ 105).

Output

For each test case, print on a line the winning digit with the maximum number of points. If there is a tie, print the minimum digit among them. If the set is empty, print  - 1.

Sample Input

2
1 2 50
20 3 10

Sample Output

3
-1

题解：给定方程式的a,b的值，求x满足y小于n的所有y的值，这些数的位数都是0~9，0~9中的数每出现一次对应加1，最后求出出现次数最多的数，如果有多个就输出最小的，如果没有满足条件的，输出-1，暴力即可。

代码如下：

#include<cstdio>
#include<cmath>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1e5 + 10;
typedef long long LL;
int s[10],ss[10];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b,n;
        scanf("%d %d %d",&a,&b,&n);
        memset(s,0,sizeof(s));
        if(a+b>n)
            printf("-1\n");
        else
        {
            for(int i=1;a*i*i+b*i<=n;i++)
            {
                int k=a*i*i+b*i;
                memset(ss,0,sizeof(ss));
                int qaq=0;
                while(k)
                {
                    ss[k%10]++;
                    qaq=max(qaq,ss[k%10]);
                    k/=10;
                }
                for(int j=0;j<=9;j++)
                    if(ss[j]==qaq)
                        s[j]++;
            }
            int z=0;
            for(int i=0;i<10;i++)
                if(s[i]>s[z])
                    z=i;
            printf("%d\n",z);
        }
    }
    return 0;
}