51nod 1770 数数字【模拟+思维】

统计一下  aaa ⋯ aaa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 对于每一组数据，输出一个整数占一行，表示答案。 Input示例 2 3 3 9 10 3 3 0 10 Output示例 10 0

思路：

1、通过手动模拟几组小数据发现（好像不用手动模拟也能知道.....）当很多很多个a*b的时候，之后会无限循环一个数.

那么我们分类讨论：

①没有进位的时候，那么a*b==d，输出n，否则输出0.

②有进位的时候，我们模拟乘法过程，直到重复出现一个数字的时候，对应在这个数字上加剩余长度。注意最高位可能和这个重复的数字不同。

Ac代码：

#include<stdio.h> #include<string.h> using namespace std; #define ll __int64 int a,b,d,n; int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&a,&b,&d,&n); if((a*b)/10==0) { if((a*b)==d)printf("%d\n",n); else printf("0\n"); } else { int pre=a*b/10; int now=a*b; int ans[10]; memset(ans,0,sizeof(ans)); ans[now]++; n--; while(n) { now=(a*b+pre); pre=(a*b+pre)/10; if(ans[now]) { ans[now]+=n; break; } else { ans[now]++; } n--; } ans[pre]++; printf("%d\n",ans[d]); } } }