# Brute-force Algorithm

Problem Description

Professor Brute is not good at algorithm design. Once he was asked to solve a path finding problem. He worked on it for several days and finally came up with the following algorithm:

Any fool but Brute knows that the function “funny” will be called too many times. Brute wants to investigate the number of times the function will be called, but he is too lazy to do it.

Now your task is to calculate how many times the function “funny” will be called, for the given a, b and n. Because the answer may be too large, you should output the answer module by P.

Input

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases.

For each test cases, there are four integers a, b, P and n in a single line.

You can assume that 1≤n≤1000000000, 1≤P≤1000000, 0≤a, b<1000000.

Output

For each test case, output the answer with case number in a single line.

Sample Input

3

3 4 10 3

4 5 13 5

3 2 19 100

Sample Output

Case #1: 2

Case #2: 11

Case #3: 12

- 点赞
- 写回答
- 关注问题
- 收藏
- 复制链接分享
- 邀请回答

*1*条回答

#### 相关推荐

- 回答 1 已采纳 Problem Description Professor Brute is not good at algorithm design. Once he was asked to solve a path finding problem. He worked on it for several days and finally came up with the following algorithm: ![](http://acm.hdu.edu.cn/data/images/3221-1.jpg) Any fool but Brute knows that the function “funny” will be called too many times. Brute wants to investigate the number of times the function will be called, but he is too lazy to do it. Now your task is to calculate how many times the function “funny” will be called, for the given a, b and n. Because the answer may be too large, you should output the answer module by P. Input There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases. For each test cases, there are four integers a, b, P and n in a single line. You can assume that 1≤n≤1000000000, 1≤P≤1000000, 0≤a, b<1000000. Output For each test case, output the answer with case number in a single line. Sample Input 3 3 4 10 3 4 5 13 5 3 2 19 100 Sample Output Case #1: 2 Case #2: 11 Case #3: 12
- 6年前回答 2 已采纳 Let's say I have a table of 100,000 MySQL records in a table with 2 columns: title and description. There's also a table containing all the bad words that need to be sanitized. For e.g. let's say the title column contains the string "Fuck this" and the profanity table says that the "Fuck" string should be replaced with "F***". Currently I implemented it with a brute force method, but this is way too slow. It checks every single substring from the sentence and compares it with every single string that exists in the profanity filter. public function sanitizeSiteProfanity($word, $replacement) { $query = $this->_ci->db->select('title, description')->get('top_sites')->result_array(); $n = $query->num_rows(); for($i = 0; $i < $n; $i++) { str_replace($word, $replacement, $query[$i]['title']); str_replace($word, $replacement, $query[$i]['description']); } } Is there a faster method to sanitize all the substrings?
- 回答 3 已采纳 I've been trying to implement the HashCash algorithm in Go! For those of you who don't know - HashCash is a method to stop spam. Basically, a header is constructed of some environment variables known both to the client and server (email, timestamp etc.). A random nonce is appended to the end of the header. The client tries to bruteforce a partial hash collision (e.g. where the first x bits are 0) by changing the nonce. HashCash works because it's not as expensive to find partial hash collisions. When the server receives this header, they verify the information in it (so it can be used only for one session) and compute the resulting hash. If the first x bits are 0, then a good amount of time has been expended on the client's machine, computing the collision (which wouldn't happen on a spambot) For me, I'm just wanting to write a program which finds the time it takes for a client to find a partial hash collision of x bits. I wrote this code which will return true/false if the int64 has a hash collision of x bits. func partialAllZeroes (zeroCount uint8, val int64) (bool, os.Error) { setBitString := "1111111111111111111111111111111111111111111111111111111111111111" unsetBitString := "0000000000000000000000000000000000000000000000000000000000000000" setBitString = setBitString[0:zeroCount-1] unsetBitString = unsetBitString[0:zeroCount-1] zeroTest, e := strconv.Btoi64(setBitString, 2) // 64 0bits zeroes, e := strconv.Btoi64(unsetBitString, 2) // 64 1bits if e != nil { return false, e } result := val & zeroTest switch { case result == zeroes: return true, nil case result != zeroes: return false, nil } return false, os.NewError("") } My current problem is I'm having alot of type conversion issues. For example, I am only able to operate on the int64 type, because that's what strconv.Btoi64 returns. Another issue that I'm also looking at is that the hash function returns as a byte array, and I have no idea how to convert that into an int64. Below is my current hash code - hasher := sha1.New() baseCollisionString := "BASE COLLISION STRING" nonce := "12345" hasher.Write([]byte(strings.Join(baseCollisionString, nonce))) testCollision := hasher.Sum() // Somehow I must convert the first x bits of testCollision into an int64 type, so I can use partialAllZeroes with it
- 回答 2 已采纳 I have read from this article http://codahale.com/how-to-safely-store-a-password/ and it says using a salt isn't even safe against GPU brute force attacks. I don't want to get hacked and have passwords decrypted in a few weeks... So I read some more and the solution was bcrypt however I don't want to implement the phpass class, I like SHA-512. However if one can add rounds to sha-512 to slow down GPU attacks... how can that be done? Does rounds mean iterations? How do you add rounds to slow down sha512?
- 回答 1 已采纳 Problem Description As you know, there number of permutation of the increasing vector {1, 2, 3…n} is exactly n! ;For example, if n = 3, then, {1,2,3} , {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} are all the permutation of the vector {1,2,3 }; We define D( {A1,A2,…An} ) = the number of element that satisfy Ai=i For example, D( {1,2,3} ) = 3 ,D( {1,3,2} ) = 1 (only ‘1’ is at 1), D({3,1,2}) = 0 …. Now we want to calculate the number of permutation that satisfy D( {A1,A2,…An} ) = K. For example, if n = 3 and k = 3, then of course there is only one permutation {1,2,3} that satisfy D( {1,2,3}) = 3. But if n = 3 and k = 0, then there are two permutations {3,1,2} and {2,3,1} satisfy D( {3,2,1} ) = D( {2,3,1} ) = 0; But when n is very large, it’s hard to calculate by brute force algorithm. Optimal is one required here. Because the answer may be very large, so just output the remainder of the answer after divided by m. Input In the first line there is an integer T, indicates the number of test cases. (T <= 500) In each case, the first line contains three integers n,k and m. (0 <= k<= n <=10^9, 1 <= m <= 10^5, n != 0) Output Output “Case %d: “first where d is the case number counted from one. Then output the remainder of the answer after divided by m. Sample Input 2 3 0 7 3 3 3 Sample Output Case 1: 2 Case 2: 1
- 4年前回答 1 已采纳 IONU Satellite Imaging, Inc. records and stores very large images using run length encoding. You are to write a program that reads a compressed image, finds the edges in the image, as described below, and outputs another compressed image of the detected edges. A simple edge detection algorithm sets an output pixel's value to be the maximum absolute value of the differences between it and all its surrounding pixels in the input image. Consider the input image below: The upper left pixel in the output image is the maximum of the values |15-15|, |15-100|, and |15-100|, which is 85. The pixel in the 4th row, 2nd column is computed as the maximum of |175-100|, |175-100|, |175-100|, |175-175|, |175-25|, |175-175|, |175-175|, and |175-25|, which is 150. Images contain 2 to 1,000,000,000 (10^9) pixels. All images are encoded using run length encoding (RLE). This is a sequence of pairs, containing pixel value (0-255) and run length (1-10^9). Input images have at most 1,000 of these pairs. Successive pairs have different pixel values. All lines in an image contain the same number of pixels. Input Input consists of information for one or more images. Each image starts with the width, in pixels, of each image line. This is followed by the RLE pairs, one pair per line. A line with 0 0 indicates the end of the data for that image. An image width of 0 indicates there are no more images to process. The first image in the example input encodes the 5x7 input image above. Output Output is a series of edge-detected images, in the same format as the input images, except that there may be more than 1,000 RLE pairs. Important Note: A brute force solution that attempts to compute an output value for every individual pixel will likely fail due to space or time constraints. Sample Input 7 15 4 100 15 25 2 175 2 25 5 175 2 25 5 0 0 10 35 500000000 200 500000000 0 0 3 255 1 10 1 255 2 10 1 255 2 10 1 255 1 0 0 0 Sample Output 7 85 5 0 2 85 5 75 10 150 2 75 3 0 2 150 2 0 4 0 0 10 0 499999990 165 20 0 499999990 0 0 3 245 9 0 0 0
- 回答 3 已采纳 Checked a lot of tutorials and guides about Encrypting and Hashing on StackOver and I do now understand the difference between both of them. Encryption when we need decryption. Hash when you don't (e.g: passwords). But my question today is, for generating random unique tokens. A lot of people recommend using base64_encode(rand_bytes(32)); because it generates a secure cryptographical id with random bytes/letters so it takes a long time to be cracked by a brute force ( to be predicted ). But when you, for example, hash_hmac or crypt that id will it make it weaker? If so it won't matter if you use mt_rand or random_bytes as it will generate other letters/id. So what do you guys recommend? Also, Is crypt better than hash_hmac for hashing? The last question, Since blowfish has a really strong hashing algorithm, do I need to store my, for example, PHPSESSID or CSRF token with it or just a normal random_bytes? Please guys, provide me with detailed information about these questions or documentation. Sorry for my lack of information and inexperience, I am new to PHP coding and thanks! Edit: I have seen some guides on SO, not covering all my questions, so I need a 2017 detailed information not a 10 years ago post where md5 was the best etc..!
- 9年前回答 1 已采纳 I have read about how to implement security into a website using hashing, and I am not creating something terribly sensitive like a bank or storing credit cards. I would, however, like to know the best practices. My site has a TLS cert with AES 256 Main issues: 1.) Sending the hashed password hashed again through the session seems to be the only way I can think of to keep the session fairly secure. In my opinion, I don't really care if the user finds that value, but I would care if the user found some way to see the database and knew exactly what my encryption algo was. 2.) Should I just completely take out my algorithm prior to hashing the password, or should I use different hashing methods? Is it okay to use sha512 prior or after bcrypt, since both of these are sound as far as collisions and brute force?
- 天使v之翼的博客 欧拉降幂 矩阵快速幂 斐波那契
- shiyuankongbu的博客 题目：hdu 3221 Brute-force Algorithm 题意：很简单，枚举几项就知道了 状态不好，sb了，错了好多遍 #include #include #include #include #include using namespace std; typedef __int64 LL; LL ...
- Harris-H的博客 Brute-force Algorithm(矩阵快速幂&欧拉降幂) 题意 a,b,ab,ab2…a,b,ab,ab^2\dotsa,b,ab,ab2… 序列的a,ba,ba,b指数是斐波那契形式，求在模ppp意义下的第nnn项。 思路 考虑先用矩阵快速幂预处理出a,ba,ba,...
- weixin_30919571的博客 对于指数取欧拉函数需要注意一下,a^x%P=a^(x%phi(P)+phi(P))%P View Code //A^x = A^(x % Phi(C) + Phi(C)) (mod C) 的应用 const int MM = 1111111; #define debug puts("wro...
- weixin_30596343的博客 5152. Brute-force Algorithm EXTREME Problem code: BFALG Please clickhereto download a PDF version of the contest problems. The problem is problem B in the PDF. But the data limi...
- 神石石的博客 写程序比较Brute-Force算法和KMP算法的效果。 SeqString.h #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef char DataType; #define MAXLEN 100 typedef struct Squeue{ ...
- zzhuao的博客 Brute-Force匹配器很简单，它取第一个集合里一个特征的描述子并用第二个集合里所有其他的特征和他通过一些距离计算进行匹配。最近的返回。 对于BF匹配器，首先我们得用cv2.BFMatcher()创建BF匹配器对象.它取两个可选...
- FDU_Nan的博客 #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) #define C 240 #define S 20 using namespace std; const int maxn = 110; struct matrix { LL mat[3]...
- Wang_128的博客 Brute-force Algorithm Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
- 因吉的博客 使用佩奇图像对Brute-force匹配器及Flann匹配器进行说明。
- Cai-Crayon的博客 Bruce-Force算法 1.思路： 简单暴力的一个算法，如果遇到字符不匹配，主串i指针回溯到本次匹配位置的下一个位置，而模式串则重新回到0（开始的位置），开始下一轮的匹配。 成功匹配的条件自然事模式串指针j...
- GAN_player的博客 使用 OpenCV 中的蛮力(Brute-Force)匹配和 FLANN 匹配。 1：Brute-Force 匹配的基础 蛮力匹配器是很简单的。首先在第一幅图像中选取一个关键点然后依次与第二幅图像的每个关键点进行(描述符)距离测试,最后返回距离...