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:
Tổng hợp các bài toán duyệt với gợi ý lời giải
Dog Show
Three strings
Lost Array
Vertical decomposition
Submask Enumeration
Palindrome
Vanya and Cubes
Minimum Euler Cycle
Coprime Permutation
Finding a negative cycle in the graph
New Year and the Permutation Concatenation
Definite Game
Transmitting Levels
D´Esopo-Pape algorithm
Josephus Problem
World Eater Brothers
Một số vấn đề đáng chú ý trong môn Tin học - Phan Công Minh
Kuroni and Impossible Calculation
Double Permutation Inc
Counting labeled graphs
Felicity's Big Secret Revealed
AND Graph
Carrot Cakes
Matching Names
Bear and Forgotten Tree 3
Factory Repairs
Calculating the determinant of a matrix by Gauss
Dima and Two Sequences
Challenging Balloons
Context Advertising
Quantifier Question