数数字

Description

 

 统计一下 aaa ⋯ aaa * b（n 个 a × b） 的结果里面有多少个数字d，a,b,d均为一位数。

样例解释：

3333333333*3=9999999999，里面有10个9。

Input

 

多组测试数据。第一行有一个整数T，表示测试数据的数目。(1≤T≤5000)接下来有T行，每一行表示一组测试数据，有4个整数a，b，d，n。 (1≤a,b≤9，0≤d≤9，1≤n≤10^9)

Output

 

对于每一组数据，输出一个整数占一行，表示答案。

Sample Input 1 

2
3 3 9 10
3 3 0 10

Sample Output 1

10
0

思路：如果a*b<10,那么不会产生进位，如果a*b=d,就有n个d，否则没有

如果a*b>=10,会产生进位，

如果n<3,直接算出来结果，判断有多少个就可以；

如果n>=3,可以发现（或者说推出）最多有4个不同的数字，

设结果从右往左1~（n+1）位，第一位会出现1次，第二位会出现1次，第（n+1）位会出现1次，剩下的都和第n位一样（即出现n-2次）   （注意：其他那三个数有可能有相同的，如：7777*8=62216），

所以我们只要求出（aaa*b），在根据规律就可以知道每个数字出现了几次。

#include<cstdio>

#include<cstring>

using namespace std;

int main(){

	int T;

	scanf("%d",&T);

	int a,b,d,n;

	while(T--){

		scanf("%d%d%d%d",&a,&b,&d,&n);

		int x,ans=0;

	    int p[10];

		if(a*b<10){

			x=a*b;

			if(x==d)

			printf("%d\n",n);

			else 

			printf("0\n");

		}

		else if(n<3){

			for(int i=1;i<=n;i++)

			ans=ans*10+a;

			ans*=b;

			int cnt=0;

			while(ans){

				x=ans%10;

				ans/=10;

				if(x==d) cnt++;

			}

			printf("%d\n",cnt);			

		}

		else {

			ans=(a*100+a*10+a)*b;

			for(int i=1;i<=4;i++){

				p[i]=ans%10;

				ans/=10;

			}

			int cnt=0;

			if(d==p[1])

			cnt++;

			if(d==p[2])

			cnt++;

			if(d==p[3])

			cnt+=n-2;

			if(d==p[4])

			cnt++;

			printf("%d\n",cnt);

		}

	}

	return 0; 

}