Difference

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 933    Accepted Submission(s): 259 Problem Description Little Ruins is playing a number game, first he chooses two positive integers y and K and calculates f(y,K) , here f(y,K)=∑z in every digits of yzK(f(233,2)=22+32+32=22) then he gets the result x=f(y,K)−y As Ruins is forgetful, a few seconds later, he only remembers K , x and forgets y . please help him find how many y satisfy x=f(y,K)−y .   Input First line contains an integer T , which indicates the number of test cases. Every test case contains one line with two integers x , K . Limits 1≤T≤100 0≤x≤109 1≤K≤9   Output For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.   Sample Input 2 2 2 3 2   Sample Output Case #1: 1 Case #2: 2

题意：

看上面的式子

题解：

将y这个数分为两半，先处理后一半，然后枚举后一半再二分查找前一半，判断是否可以满足上面的式子

题目卡时间看的很气，数组开 long long  不行，会超时

并且再指数次方的那里需要预处理，并且不能先处理前一半，因为后一半和前一半有乘以100000的一个关系，利用好又可以减少时间

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define maxn 100005 #define LL long long int a[maxn],sum[20][20],num[maxn]; int main() { for(int i=1;i<10;i++){ sum[i][0]=1; for(int j=1;j<=9;j++){ sum[i][j]=sum[i][j-1]*i; } } int T; int cases=1,x,k,temp,pos; //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { LL t; pos=0; scanf("%d%d",&x,&k); memset(num,0,sizeof(num)); for(int i=1;i<100000;i++){ temp=i; while(temp) { num[i]+=sum[temp][k]; temp/=10; } a[pos++]=num[i]-i; } sort(a,a+pos); LL ans=0; for(LL i=0;i<100000;i++){ t=num[i]-i*100000; t=x-t; temp=lower_bound(a,a+pos,t)-a; while(a[temp]==t&&temp<pos) ans++,temp++; } printf("Case #%d: %lld\n",cases++,ans); } return 0; }