Statement:

HOJ 13375(Origin: HNU Contest)

In this case, I discussed with my classmates and only gave my solution.

Multiple of 7

Time Limit: 1000ms, **Special Time Limit:**2500ms, **Memory Limit:**65536KB

Total submit users: 127, Accepted users: 62

Problem 13775 :

No special judgement

Problem description

Give you an integer such as abab….. with length n. where a,b are digit.1< = a < = 9, 0< = b < = 9. Your task is to answer whether the given integer is multiple of 7.

For example, 3535,343,141414 are multiples of 7,and 121,11,2,232 are not.

Input

There are multiple test cases, the first line contain an integer T, the number of test cases. 1 < = T < = 1000.

Each test case contains 3 integers in one line: a,b,n.

1< = a < = 9, 0< = b < = 9, 1< = n < = 10^9.

Output

For each test case, output “Yes” if the integer is multiple of 7, otherwise output “No”.

Sample Input

3, 1, 2, 3, 3, 5, 4, 3, 4, 3Copy the code

Sample Output

No
Yes
Yes
Copy the code

Judge Tips

The first case 121 is not multiple of 7,the 2nd and 3rd ,3535 and 343 are multiples of 7.

Problem Source

HNU Contest 

Data range: 1<=a<=9,0<=b<=9,1<=n<=1e9

The maximum acceptable time complexity is O(logn), but it cannot be realized. Moreover, the nature of digital loop cannot construct array traversal. There are two solutions:

Time complexity O(n%6), also thought of as O(1)

The input number can be decomposed as follows:

Thus, the problem we solved can be translated into the following questions:

We follow lemma 1:

We can also graph lemma 1: f(k) is a discrete periodic function.

According to Lemma 1, it follows that

We found that:

That is, for such an integer of length n, modulo 7, the lowest digit can be cancelled out every six bits, and only the remaining high digit can be considered.

Such as:

35353535mod7=35mod7

4444444444mod7=4444mod7

There are many ways to implement it. Therefore, the time complexity can be O(n%6) or O(1) depending on the implementation.

Notice which of a and B is multiplying the odd digit and which is multiplying the even digit.

Answer key:

# include < stdio, h > const int div [6] =,3,2,6,4,5 {1}; int t,a,b,n,ans; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d%d",&a,&b,&n); n=n%6; switch(n){ case 0:ans=0; break; case 1:ans=a*div[0]; break; case 2:ans=b*div[0]+a*div[1]; break; case 3:ans=a*(div[0]+div[2])+b*div[1]; break; case 4:ans=b*(div[0]+div[2])+a*(div[1]+div[3]); break; case 5:ans=a*(div[0]+div[2]+div[4])+b*(div[1]+div[3]); break; } printf(ans%7==0?" Yes\n":"No\n"); }}Copy the code