大数阶乘，大数的排列组合等，一般都要求将输出结果对1000000007取模（取余）
为什么总是1000000007呢= =
大概≖‿≖✧是因为：（我猜的，不服你打我呀~）
1. 1000000007是一个质数（素数），对质数取余能最大程度避免冲突～
2. int32位的最大值为2147483647，所以对于int32位来说1000000007足够大
3. int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出
所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出
｡◕‿◕｡
|
1 2 3 4 5 6 7 8 |
库函数里面的sqrt有三个原型 double sqrt(double); float sqrt(float); long double sqrt(long double); 没有int sqrt(int); 所以k=sqrt(x);改为k=sqrt((double)x);就可以通过编译了。 ——度娘。ヾ(=^▽^=)ノ |
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 15440 | Accepted: 8707 |
Description
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don’t know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on… Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
Input
Output
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 24137 | Accepted: 9997 | Special Judge | ||
Description
Input
Output
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
poj1207-The 3n + 1 problem Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 55398 Accepted: 17651 Description Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs. Consider the following algorithm: 1. input n 2. print n 3. if n = 1 then STOP 4. if n is odd then n <-- 3n+1 5. else n <-- n/2 6. GOTO 2 Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.) Given an input n, it is possible to determine the number of numbers printed before the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16. For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j. Input The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 10,000 and greater than 0. You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j. Output For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line). Sample Input 1 10 100 200 201 210 900 1000 Sample Output 1 10 20 100 200 125 201 210 89 900 1000 174 #include <iostream> using namespace std; int main() { int a, b; while (cin >> a >> b) { int max = 0; int low = a > b ? b : a; int high = a > b ? a : b; for (int i = low; i <= high; i++) { int cou = 1; int t = i; while (t != 1) { if (t % 2 == 1) { t = 3 * t + 1; } else t = t / 2; cou++; } if (cou > max) { max = cou; } } cout << a << " " << b << " " << max << endl; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
POJ-2488 A Knights Journey-深度优先搜索 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 37974 Accepted: 12896 Description Background The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? Problem Find a path such that the knight visits every square once. The knight can start and end on any square of the board. Input The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . . Output The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number. If no such path exist, you should output impossible on a single line. Sample Input 3 1 1 2 3 4 3 Sample Output Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4 Source TUD Programming Contest 2005, Darmstadt, Germany #include <iostream> using namespace std; int next1[8][2]={ {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1} }; //记录方向 int a, b, flag; int book[26][26], path[26][2]; void dfs(int i, int j, int k) { if (k == a * b) { for (int t = 0; t < k; t++) { printf("%c", path[t][0] + 'A'); cout << path[t][1]+1; } cout << endl; flag = 1; } else { for (int t = 0; t < 8; t++) { int n = i + next1[t][0]; int m = j + next1[t][1]; if (n >= 0 && n < b && m >= 0 && m < a && book[n][m] == 0 && flag == 0) { book[n][m] = 1; path[k][0] = n; path[k][1] = m; dfs(n, m, k + 1); book[n][m] = 0; } } } } int main() { int N; cin >> N; for (int m = 0; m < N; m++) { flag = 0; cin >> a >> b; for (int i = 0; i < a; i++) for (int j = 0; j < b; j++) book[i][j] = 0; book[0][0] = 1; path[0][0] = 0,path[0][1] = 0; cout << "Scenario #" << m + 1 << ":" << endl; dfs(0, 0, 1); if (!flag) cout << "impossible" << endl; cout << endl; } return 0; } |