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:
Heroes of Making Magic III
Helping People
Not Wool Sequences
Om Nom and Necklace
Triangle
M-numbers
Clockwork Bomb
Escaping on Beaveractor
Flowers and Chocolate
Fair
Sereja and the Arrangement of Numbers
Berland Elections
Bad Days
Lowest Common Ancestor - Farach-Colton and Bender Algorithm
Intersecting Subtrees
Submask Enumeration
Robot Rapping Results Report
Simple Skewness
Captains Mode
Promocodes with Mistakes
Euler's totient function
Fox And Polygon
Movie Fan
Extended Euclidean Algorithm
Finding articulation points in a graph in $O(N+M)$
Xenia and Colorful Gems
Solve RMQ (Range Minimum Query) by finding LCA (Lowest Common Ancestor)
Casinos and travel
Looksery Party
Cow and Treats
Orac and Game of Life
Haar Features