首页 > 代码库 > HUST 1599 Multiple
HUST 1599 Multiple
Multiple
Time Limit: 2 Sec Memory Limit: 64 MBSubmissions: 197 Solved: 35
Description
Rocket323 loves math very much. One day, Rocket323 got a number string. He could choose some consecutive digits from the string to form a number. Rocket323loves 64 very much, so he wanted to know how many ways can he choose from the string so the number he got multiples of 64 ?
A number cannot have leading zeros. For example, 0, 64, 6464, 128 are numbers which multiple of 64 , but 12, 064, 00, 1234 are not.
Input
Multiple cases, in each test cases there is only one line consist a number string.
Length of the string is less than 3 * 10^5 .
Huge Input , scanf is recommended.
Output
Print the number of ways Rocket323 can choose some consecutive digits to form a number which multiples of 64.
Sample Input
64064
Sample Output
5
HINT
There are five substrings which multiples of 64.
[64]064
640[64]
64[0]64
[64064]
[640]64
题目大意是:给出一个串,求有多少个子串(无前导0)能被64整除。
分析:单独的一个子串“0”肯定是的,再暴搜子串字符个数为2、3、4、5、6的能被64整除的,1000000%64==0。
所以字符个数为6的可以整除64的可以特殊判断一下:
高位为0,那么他本身不符合(有前导0),但在它前面加任意一个不为0的数都能整除64。所以加上他前面不为0的数字个数。
高位不为0,那么再加上它本身这一种。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 6 typedef __int64 LL; 7 const int maxn=300005; 8 char text[maxn]; 9 int d[maxn]; 10 11 void solve() 12 { 13 int i,len=strlen(text); 14 if(text[0]==‘0‘) d[0]=1; 15 else d[0]=0; 16 for(i=1;i<len;i++) 17 { 18 if(text[i]==‘0‘) d[i]=d[i-1]+1; 19 else d[i]=d[i-1]; 20 } 21 LL ans=d[len-1]; 22 for(i=len-1;i>=1;i--) 23 if(text[i-1]!=‘0‘ && ((text[i-1]-‘0‘)*10+text[i]-‘0‘)%64==0) ans++; 24 for(i=len-1;i>=2;i--) 25 if(text[i-2]!=‘0‘ && ((text[i-2]-‘0‘)*100+(text[i-1]-‘0‘)*10+text[i]-‘0‘)%64==0) ans++; 26 for(i=len-1;i>=3;i--) 27 if(text[i-3]!=‘0‘ && ((text[i-3]-‘0‘)*1000+(text[i-2]-‘0‘)*100+(text[i-1]-‘0‘)*10+text[i]-‘0‘)%64==0) ans++; 28 for(i=len-1;i>=4;i--) 29 if(text[i-4]!=‘0‘ && ((text[i-4]-‘0‘)*10000+(text[i-3]-‘0‘)*1000+(text[i-2]-‘0‘)*100+(text[i-1]-‘0‘)*10+text[i]-‘0‘)%64==0) ans++; 30 for(i=len-1;i>=5;i--) 31 { 32 if(((text[i-5]-‘0‘)*100000+(text[i-4]-‘0‘)*10000+(text[i-3]-‘0‘)*1000+(text[i-2]-‘0‘)*100+(text[i-1]-‘0‘)*10+text[i]-‘0‘)%64==0) 33 { 34 if(text[i-5]!=‘0‘) ans++; 35 if(i-5>0) ans+=i-5-d[i-5-1]; 36 } 37 } 38 printf("%I64d\n",ans); 39 } 40 int main() 41 { 42 while(gets(text)) 43 { 44 solve(); 45 } 46 return 0; 47 }