HUST 1599 Multiple

Multiple

Time Limit: 2 Sec Memory Limit: 64 MB
Submissions: 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

Sample Output

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
",ans);
39 }
40 int main()
41 {
42     while(gets(text))
43     {
44         solve();
45     }
46     return 0;
47 }