vector <int> mas = {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, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161}; //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; vi v = {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, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161}; int main() { int n, x; cin >> n; fo(i, n) { cin >> x; cout << v[x - 1] << '\n'; } } Should I use some test of simplicity (from Cormen or somewhere else) or is there any better way for such numbers? If someone knows how to solve this proble without cheatin' (if carefull reading of the definition is a cheat) then he can get a lot of money... :) Sorry, I understood after all, as for me I just found all the numbers in the Internet:) Of course, you cannot solve it without "cheating". The most powerful tests work for months to test one number! You already have all numbers written in the text - why do you think it is cheating? And it's easy to find the rest - up to 7-th. It's enough to test all numbers 2^p-1 up to 2^30-1 (only 30 numbers!) using bruteforce. I don't think it is possible to solve it without cheating, otherwise, why now the largest one is only 43th? Any way, you can get most of the ans in the text, except 3~8... its just impossible to calculate it in 1 second. If using Wikipedia and OEIS aren't cheating I know how to do it) If using Wikipedia and OEIS aren't cheating I know how to do it) Using Wikipedia and OEIS may be cheating, but using the answers already in the problem definition definitely isn't. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; using System.Threading.Tasks; namespace T1 { class Program { static void Main(string[] args) { int n = int.Parse (Console.ReadLine ()); int[] data = new int[]{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, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161}; int[] result = new int[n]; for (int i = 0; i < n; ++i) result [i] = data [int.Parse (Console.ReadLine ()) - 1]; for (int i = 0; i < n; ++i) Console.WriteLine (result [i]); } } } The largest known prime number is currently the Mersenne prime 2^{57,885,161} - 1. Discovered January, 2013. Edited by author 12.12.2013 01:30 this problem is easy Edited by author 30.10.2013 13:06 Thanks for the excellent reference. My alternative was to precalculate in an array, as time always exceeded 1 second. This code get 0.001 int main() { int n, i, k, m[]={ 0, here must be numberz :) }; // 39 numbers scanf("%d",&k); for(i=0;i<k;i++) { scanf("%d",&n); printf("%d\n",m[n]); } return 0; } and this code get 0.015 int main() { int n, i, k, m[]={here must be numberz :) }; // 38 numbers scanf("%d",&k); for(i=0;i<k;i++) { scanf("%d",&n); printf("%d\n",m[n-1]); } return 0; } Why 38 iterations of (n-1) so hardly influence for speed of execution ??? Edited by author 02.05.2007 01:47 It is not a problem of time, your program is good.You have different time because the server was checking another solution with yours Edited by author 18.02.2010 20:17 If the only method possible is cheating, what is the point in giving such problems. It doesnt test anything. So, after you cheat it, you can get to know - what is it, Mersenne primes cos I, for example, don't know what is it before reading this problem =) In the first string of condition: "For example, 2^2−1 — the first Mersenne prime". So, the first Mersenne prime is 2^2-1 = 3. Then, in the sample we read: 18 - 3217 But, if so, the first Mersenne prime is 2, not 3, so, for the test 1 1 the program should output 2, not 3. 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; Is it all right? Cuz I got WA... Help me. Yes the sequence is correct. I don't know what is wrong. There must be a problem with your code Const ... {sequence} Var n:array[1..40] of byte; t,i:byte; Begin Readln(t); For i:=1 to t do Readln(n[i]); For i:=1 to t do Writeln(a[n[i]]); END. I cann't believe it! I Have TLE#4! You hands is normal? :) I'm asking for help. What do you mean "hands". Try printing the output as soon as you read it. You don't know the exact limit for T. So your program behaves abnormally for T>40. Thank you! I got AC! Thanks. Thanks for the author!!! Edited by moderator 10.01.2007 00:32 :-)))))))))))))))))))000!!! Edited by author 25.05.2008 14:57 oh no wa#1 noooooo #include <mat.h> #include <iostream.h> int man(){ coout<<"NOOOOOOO"; } Edited by author 14.04.2007 21:49 Variants 1) find/stole supercomputer) 2) find big numbers in text and small count yourself 3) for lazy: find all numbers in internet I GO BY 3-RD WAY,HERE IS SOLUTION: [DELETED] Edited by author 14.04.2007 22:21 ОГРОМНОЕ СПАСИБО СЕР. Я в принципе тоже так решал только напутал коэффициенты поэтому получил WA#1 и плюнул. Я твой должник, скажи с какой задачей тебе помочь? NE ZA CHTO.UDACHI!!!WHEN I SOLVED THIS PROBLEM AND WHEN I DID COUT ,I FORGOT ENDL!FUNNY,ISN'T IT?BUT NOW I HAVE AC!!! Edited by author 14.04.2007 22:24 Edited by author 14.04.2007 22:24 #include <iostream.h> #include <math.h> int prost(int a) { int kol=0; for(int i=2;i<=int (sqrt(a));i++) { if(a%i==0) kol++; } if(kol==0) return 1; else return 0; } int main() { int T,n,kol=0,i=0,p=2; cin>>T; for(int j=0;j<T;j++) { cin>>n; while(i!=n) { if((prost(pow(2,p)-1))==1) { i++; } if(i==n) { cout<<p<<' '; } p++; }
} return 0; } All Mersenne primes you can find in text of problem... Good luck!.. Edited by author 28.03.2007 00:35 N cannot be >40. And when you replaced stream IO with formatted it didn't fix your main mistake :) Your solution still works incorrect on sample test. You will be veeeery surprised when will find it :-D [code deleted] Edited by moderator 28.07.2006 10:35 why do you think that n<=40 ? N may be greater than 40! You should not use array. All necessary numbers are given in task (for all n>8), so the only task is to find first 7 numbers!!! So, this problem can be solved without cheating :) PS. Thanks for Link! Edited by author 08.07.2006 19:52 it depends on what you understand as cheating;) But it is no other way to solve this task other then using control c control v;))) |
|