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:
Integration by Simpson's formula
Banners
Nikita and stack
Balanced Ternary
Ksusha and Square
Balanced bracket sequences
Count the Arrays
Yuhao and a Parenthesis
Bots
Optimal schedule of jobs given their deadlines and durations
TorCoder
New Year Book Reading
Run for beer
Dirty Deeds Done Dirt Cheap
Haar Features
Wise Men (Easy Version)
Startup Funding
Primitive Root
Rectangle Puzzle
Little Artem
Delaunay triangulation and Voronoi diagram
Heavy-light decomposition
Paint the String
Merging Two Decks
Finding Intersection of Two Segments
Princesses and Princes
Optimal Subsequences (Hard Version)
Treap (Cartesian tree)
Three Blocks Palindrome
Playing on Graph
Tricky Interactor
Bear and Poker