关键词:
1118. Nontrivial Numbers
Memory limit: 64 MB
Input
Output
- I ≤ N ≤ J;
- N is the least trivial number among the ones that obey the first condition.
Sample
input | output |
---|---|
24 28
|
25
|
Problem Author: Leonid Volkov
Problem Source: USU Open Collegiate Programming Contest October‘2001 Junior Session
题目描述:在区间a <= k <= b, triviality(k) = (Σ(k的因子) - k)/k, 求k使得triviality(k)最小
思路:(1)如果a = 1, 最小的是1,triviality(1) = 0 ;
(2)如果区间内有素数, 那么取值当然是最大的素数了;
(3)打个素数表暴力判断。。
1 #include <iostream> 2 #include <sstream> 3 #include <fstream> 4 #include <string> 5 #include <vector> 6 #include <deque> 7 #include <queue> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <algorithm> 12 #include <functional> 13 #include <utility> 14 #include <bitset> 15 #include <cmath> 16 #include <cstdlib> 17 #include <ctime> 18 #include <cstdio> 19 #include <string> 20 using namespace std; 21 int N, T; 22 const int M = 1e6+5; 23 bool a[M]; 24 int prime[M]; 25 int cnt = 0; 26 void init() { 27 for(int i = 2; i < M; i++) a[i] = true; 28 for(int i = 2; i < M; i++) { 29 if(a[i]) { 30 cnt++; 31 prime[cnt] = i; 32 } 33 for(int j = 1; j <= cnt; j++) { 34 if(i * prime[j] >= M) break; 35 a[i*prime[j]] = false; 36 if(i % prime[j] == 0) break; 37 } 38 } 39 } 40 int main() { 41 //freopen("in.txt", "r", stdin); 42 init(); 43 int r, l; 44 scanf("%d%d", &l, &r); 45 double s = 1e9; 46 int res = 0; 47 for(int k = r; k >= l; k--) { 48 if(a[k]) { 49 res = k; 50 break; 51 } 52 } 53 if(l == 1) printf("1 "); 54 else if(res > 0) printf("%d ", res); 55 else { 56 for(int k = l; k <= r; k++) { 57 double sum = 1; 58 int i; 59 for(i = 2; i*i < k; i++) { 60 if(k%i == 0) { 61 sum += i + k/i; 62 } 63 } 64 if(i*i == k) sum += i; 65 if(sum/k < s) { 66 s = sum/k; 67 res = k; 68 } 69 } 70 printf("%d ", res); 71 } 72 return 0; 73 }
ural2020trafficjaminflowertown
2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情
ural1424minibus
MinibusTimelimit:1.0secondMemorylimit:64MBBackgroundMinibusdriverSergeyA.Greedsonhasbecometotallyfamousforhisphenomenalgreediness.Heclaimedtimeandagainthatheheldhimselfinreadinesstothrottlehisbrothera 查看详情
ural1855tradeguildsoferathia
TradeGuildsofErathiaTimelimit:2.0secondMemorylimit:64MBThecontinentofAntagarichwascolonizedslowly.LongagoitsnorthernpartwasinhabitedbytheelvesofAvlee.Later,thehotsoutherndesertofBracadawasoccupiedbyth 查看详情
ural2016magicandscience
2016.MagicandScienceTimelimit:1.0secondMemorylimit:64MBScientistswhospecializeinwitchcrafthaverecentlydiscoveredanewelementaryparticlecalledamagion.Studyingthelawsofmagions’movement,agroupofthre 查看详情
ural2021scarilyinteresting!
2021.Scarilyinteresting!Timelimit:1.0secondMemorylimit:64MBThisyearatMonstersUniversityitisdecidedtoarrangeScareGames.AttheGamesallcampusgathersatthestadiumstands,andtheScareprogramstudentsdivideintot 查看详情
[ural1519]formula1
[URAL1519]Formula1试题描述Regardlessofthefact,thatVologdacouldnotgetrightstoholdtheWinterOlympicgamesof20**,itiswell-known,thatthecitywillconductoneoftheFormula1events.Surely,forsuchanimportantthinganewra 查看详情
ural1118.nontrivialnumbers
1118.NontrivialNumbersTimelimit:2.0secondMemorylimit:64MB SpecialistsofSKBKonturhavedevelopedauniquecryptographicalgorithmforneedsofinformationprotectionwhiletransmittingdataovertheInternet.Thema 查看详情
ural2015zhenyamovesfromthedormitory
2015.ZhenyamovesfromthedormitoryTimelimit:1.0secondMemorylimit:64MBAftermovingfromhisparents’placeZhenyahasbeenlivingintheUniversitydormitoryforamonth.However,hegotprettytiredofthecurfewtimeandq 查看详情
ural2017bestofabadlot
2017.BestofabadlotTimelimit:1.0secondMemorylimit:64MBAcruiselinerhasn’tmovedawayfromthelandevenforthreemileswhenitbecameapparentthatsomebodyhasdrownedoneofthestewardsintheswimmingpool.Thecaptain 查看详情
ural2012aboutgrishan.
2012.AboutGrishaN.Timelimit:1.0secondMemorylimit:64MBGrishaN.toldhistwoteammatesthathewasgoingtosolveallgivenproblemsatthesubregionalcontest,eveniftheteammateswouldn’tshowupatthecompetition.Thet 查看详情
ural2014zhenyamovesfromparents
2014.ZhenyamovesfromparentsTimelimit:1.0secondMemorylimit:64MBZhenyamovedfromhisparents’hometostudyinothercity.Hedidn’ttakeanycashwithhim,heonlytookhisfather’screditcardwithzerobalan 查看详情
ural2022ridingatoad
2022.RidingaToadTimelimit:1.0secondMemorylimit:64MBAtribeofleafmenliveintheoldforest.Leafmenareverytinyandfast,that’swhywecan’tnoticethemevenwhentheyareunderourverynose.Leafmenguardthefore 查看详情
ural1196.historyexam(二分)
1196.HistoryExamTimelimit:1.5secondMemorylimit:64MBProfessorofhistorydecidedtosimplifytheexaminationprocess.Attheexam,everystudentshouldwritealistofhistoricdatessheknows(sheshouldwritetheyearsonlyand, 查看详情
ural1224.spiral(规律)
1224.SpiralTimelimit:1.0secondMemorylimit:64MBAbrandnewsapperrobotisabletoneutralizeminesinarectangularregionhavingintegerheightandwidth(NandMrespectively).Beforetherobotbeginsitsworkitisplacednearthe 查看详情
ural2031.overturnednumbers(枚举)
2031.OverturnedNumbersTimelimit:1.0secondMemorylimit:64MBLittlePierrewassurfingtheInternetandcameacrossaninterestingpuzzle:Whatisthenumberunderthecar?IttooksometimebeforePierresolvedthepuzzle,butevent 查看详情
ural1081binarylexicographicsequence(递归)(代码片段)
URAL1081.BinaryLexicographicSequenceTimelimit:0.5secondMemorylimit:64MBDescriptionConsiderallthesequenceswithlength(0<N<44),containingonlytheelements0and1,andnotwoonesareadjacent(110isnotavalids 查看详情
ural1343.fairytale打表
1343.FairyTaleTimelimit:1.0secondMemorylimit:64MB 12monthstosinganddanceinaringtheircelestialdance.Oneafteranothertheyholdathrone.ThefirstisyoungandfierceJanuaryandthelastiselderlyandwiseDecember 查看详情
ural1427sms
URAL1427思路:贪心。很水的一道贪心,找bug找了很久,没有考虑到n=1的情况。代码:#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definepbpush_back#definemem(a,b)memset(a,b,sizeof(a))chars[100005];intmain(){/*ios::sync_ 查看详情