Consider the following equation:where sign [a] represents the integer part of number a.
Let’s find all integer z (z > 0), for which this equation is unsolvable in positive integers. The phrase “unsolvable in positive integers” means that there are no such positive integers x and y (x, y > 0), for which the given above equation holds.
Let’s write out all such z in the increasing order: z 1, z 2, z 3, and so on (z i < z i + 1). Your task is: given the number n, find the number z n.
Input
The first line contains a single integer n (1 ≤ n ≤ 40).
Output
Print a single integer — the number z n modulo 1000000007 (109 + 7). It is guaranteed that the answer exists.
Examples
input
1
output
1
input
2
output
3
input
3
output
15
Solution:
#include <iostream> #include <iomanip> #include <stdio.h> #include <set> #include <vector> #include <map> #include <cmath> #include <algorithm> #include <memory.h> #include <string> #include <sstream> using namespace std; const int md = 1000000007; int a[40] = {2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,19937,21701,23209,44497, 86243,110503,132049,216091,756839,859433,1257787,1398269,2976221,3021377,6972593,13466917,20996011}; int main() { // freopen("in","r",stdin); // freopen("out","w",stdout); int n; scanf("%d",&n); int x = 1; for (int i=1;i<a[n-1];i++) { x *= 2; if (x >= md) x -= md; } printf("%d\n",(x+md-1) % md); return 0; }
Related posts:
Wheels
Felicity's Big Secret Revealed
Unusual Graph
Landmarks
Cheap Travel
Bracket Sequence
Maximum flow - Ford-Fulkerson and Edmonds-Karp
Tricky Interactor
New Year Letter
Limericks
Fountains
Vladislav and a Great Legend
Number of divisors / sum of divisors
Memory for Arrays
Calculating the determinant using Kraut method in $O(N^3)$
Deleting from a data structure in $O(T(n)\log n)$
Strange Function
Playing with Permutations
Sieve of Eratosthenes Having Linear Time Complexity
Euler's totient function
More Reclamation
Festival Organization
Chip Game
New Year and the Acquaintance Estimation
Deduction Queries
Xenia and Colorful Gems
Elections
Good Subsets
Fence
Falling Blocks
Optimal Point on a Line
Paint the edges of the tree