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:
Rational Resistance
Bad Ugly Numbers
Ordering T-Shirts
A Trivial Problem
Epic Convolution
Little Artem and Random Variable
Count The Blocks
Big Secret
Replicating Processes
And Yet Another Bracket Sequence
Lowest Common Ancestor
Expression parsing
The Inclusion-Exclusion Principle
Parity
Network Topology
Correcting Mistakes
Suffix Tree. Ukkonen's Algorithm
Kuroni and Impossible Calculation
Randomized Heap
Magic multisets
Encoding
Packets
Topological Sorting
Paint the Numbers
Design Tutorial: Learn from a Game
Purification
Half-plane intersection - S&I Algorithm in O(Nlog N)
Bash's Big Day
Vanya and Lanterns
Bits And Pieces
Treasure
PE Lesson