Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

function do_test($input, $expected_output)
{
	global $task_id;
	exec("echo '$input' | Solutions2/bin/$task_id &2>1", $output);
	if(count($output)==0)return false;
	return(strcmp($output[0], $expected_output)==0);
}

$result = do_test("10","17") && do_test("1","0") && do_test("1000","76127") && do_test("100000","454396537") && do_test("1000000","37550402023");

$start_time = microtime (true);
//for($i=0;$i<100;$i++)
	$result = do_test("980000000","23783220704190493") && do_test("1051174931","27269025983026043") && do_test("891728152","19783994900202129") && do_test("761987760","14559966509022149");
$end_time = microtime (true);

//@shadeware
#include <cstdio>
#include <vector>
#include <cmath>
unsigned i,n,Q,j,L;long long u[66],A;int main(){for(;i<448;i++)u[i/7+2]=u[i/7+2]*96+"+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22'X S'}2"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|'F^1R`5'k)0{z2\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c"<0dAd/tP1->"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X'W4 13M.MfL0"
"5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0'"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i]-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u[i];scanf("%u",&n);Q=sqrt(n)+1e-7,L=n>>24<<24;A=u[(n>>24)+1]+2*!L*!!~-n;std::vector<bool>S(Q/2+1),B(n-L+2);B[1]=!L;for(i=3;i<=Q;i+=2)if(!S[i/2]){for(j=3*i;j<=Q;j+=2*i)S[j/2]=1;for(j=L?(L+i-1)/i*i:2*i;j<=n;j+=i)B[j-L]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llun",A);} 

//@mikhaelkh
#include <cstdio>
#include <bitset>
unsigned char s[]=" 3ћfСЫБ b”Ђ)Cр ®—іЈ€Я $9шэD » $ѕ|Іш®† %ЃЉЃмF© &_яВГЕЕ 'Y¶FьВµ (nsџИp± )ќлznQ2 *иSР—ж) ,oшtе\v -пW0BC† /«Ю#™)ґ 1‚ьј”8P 3sю[Y6i 5.qЛ.“ 7¤zMЃшj 9г—‹XyЇ <_‰­XжЅ >ТOh«€Y AЃМ“«n® DKr]µrЩ G.?“нU® J*Ј»‚­Џ M@˜Eп†Ь PpYґпHј S№pvdјя W>дGpІш ZєQЦаЋ~ ^qяmty= bC†,щnт f.d“¤ ¤ j1Ж [|Ј nN№BўЮ: r…ЄG­рр vФiчwЁ{ {_Лз}Lh б*sЁЭ# „ћoї‹УE ‰to]¶е~ Ћd*4:иХ “kѕK8ћш ˜Њ~ќ˜QЄ ќЕЛ7д6« Ј;Ёл0ўь Ё§Iвc§б ®ObЗюЏP імЏxь>† №Е›»ЯPo ї·NцбЬ† ЕБ1ґgп& ЛгlъІcѓ ТAdЎ“[$ Ш–Й:ілЧ Я%юі±Ю1 е«_7бќЌ мlчnєСџ уF”ЭDРЭ ъ8ћуcћЖ $$CМжМMЕ $+gDbцPр $2ЎЧтУ‡E $9цА®П†Ы ";
enum{S=1<<14,N=1<<23};
long long a[65],res;
std::bitset<S> u;
std::bitset<N> v;
int n,r,x,i,j;
int main() {
	scanf("%d",&n);
	for (i=1;i<65;++i)
		for (++j;s[j]>32;++j)
			a[i]=221*a[i]+s[j]-35;
	*a=2,res=a[j=n/2/N],x=j*2*N,v[0]=!j;
	for (i=3;i<S+S;i+=2)
		if (!u[i/2]) {
			for (j=i*i/2;j<S;j+=i)u[j]=1;
			for (j=(x?((r=i-x%i)&1?r:r+i):i*i)/2;j<N;j+=i)v[j]=1;
		}
	for(i=1;i<=n-x;i+=2)
		if(!v[i/2])res+=x+i;
	printf("%lldn", n>1?res:0);
}

//@Icemore
#include<iostream>
#include<cmath>
#include<memory.h>
#include<pthread.h>
#define lng long long
const int T=4,Q=33000,S=100000;
bool np[Q],b[T][S];
int p[Q],c,B,s,e;
lng A[T],R,P[]={0,1906816620981654LL,7357074544482779LL,16217881619242062LL,28422918403819825LL};
void* f(void*_){
	long id=(long)_;
	int C=(e/S-B+1)/T,q,M,i,j,k;
	M=(id==T-1)?(e/S+1):(id+1)*C+B;
	for(k=id*C+B;k<M;++k){
		memset(b[id],0,sizeof(bool)*S);q=k*S;
		for(i=0;i<c;++i){
			j=(q+p[i]-1)/p[i];j=(j>1?j:2)*p[i]-q;
			for(;j<S;j+=p[i])b[id][j]=1;
		}
		if(!k)b[id][0]=b[id][1]=1;
		for(i=std::max(0,s-q);i<S&&q+i<=e;++i)if(!b[id][i])A[id]+=q+i;
	}
	return 0;
}
int main(){
	int n,i,q,j;
	std::cin>>n;
	i=(n-1)/(1<<28);s=i*(1<<28)+2;e=(i+1)*(1<<28);
	if(n-s-1<e-n)R=P[i],e=n;else s=n+1,R=-P[i+1];
	B=s/S;q=(int)sqrt(e+.0);p[c++]=2;
	for(i=3;i<=q;i+=2)if(!np[i])for(j=i*i,p[c++]=i;j<=q;j+=i)np[j]=1;
 	pthread_t t[T];
	for(i=0;i<T;++i)pthread_create(t+i,0,f,(void*)(i));
	for(i=0;i<T;++i)pthread_join(t[i],0),R+=A[i];
	std::cout<<(R>0?R:-R);
} 

//@ripatti
//идея - блочное решето с предпросчетом ответов для нескольких первых блоков
#include <iostream>
#include <memory.h>
#define S 150000
bool F[40000],B[S];
int P[10000],p=0;
long long pre[]={0,79835127420606,307011790722811,675490692294675,
1182357709860117,1825666731904492,2603717273255596,3515373254256955,
4559774703609068,5736228298250417,7043215380181465,8481171232603598,
10049045128993920,11745741297705187,13571569117886223,15525668198679060,
17608378509778587,19817357312226874,22154562782502270,24618987306923167,
27209541722648039};
int main(){
	int a,b,c,n,Z=(1<<15),Q=S*350;
	std::cin >> n;
	long long ans=pre[n/Q];
	for(a=2;a*a<Z;a++)if(!F[a])for(b=a*a;b<Z;b+=a)F[b]=true;
	for(a=2;a<Z;a++)if(!F[a])P[p++]=a;
	for(a=(n/Q)*Q;a<=n;a+=S){
		memset(B,0,sizeof B);
		for(b=0;b<p;b++)for(c=std::max(2,(a+P[b]-1)/P[b])*P[b]-a;c<S;c+=P[b])B[c]=true;
		if(a==0)B[0]=B[1]=true;
		for(b=0;b<S&&a+b<=n;b++)if(!B[b])ans+=a+b;
	}
	std::cout << ans;
	return 0;
}

//@kbxxi
#include <iostream>
long long A[]={0,72619548630277,279209790387276,614333144695291,1075207199997334,1660170771905893,2367646772295462,
3196703482711201,4146437503168147,5215984059716389,6404774487532576,7711724083073573,9137303389808024,
10680189372387880,12340337443955708,14116726304047228,16010026481858292,18019518580817005,20143329357815162,
22383876593236984,24739512092254535,27209541722648039};
char S[50000100];
int p[50100],C,i,j,B=50000000,l,r;
long long R=0;   

int main(){    
	std::cin >> r;   
    for (i=2;i<=100000;i++)
    if (!S[i]){
        p[C++]=i;        
        for (j=2*i;j<=100000;j+=i)
            S[j]=1;
    } else S[i]=0;    
	l=r/B*B+1;
	for (i=1;p[i]*p[i]<=r;i++){
        int v=p[i],P=l/v*v;        
        if (P<l) P+=v;
		if (P==v) P+=v;
		if (!(P&1)) P+=v;
		v*=2;
        while (P<=r) S[P-l]=1,P+=v;        
    }
    for (i=l;i<=r;i+=2) if (!S[i-l] && i!=1) R+=i;
	if (l==1 && r>1) R+=2;
    std::cout<<A[r/B]+R;	
	return 0;
}

//@singstio
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main()
{
  __int64_t n,sum=0,i,j,sn;
  cin>>n;
  sn=int(sqrt(n))+1;
  vector<bool> s(n+1,true);
  for(i=2;i<=sn;i++)
    if(s[i]){
      for(j=i*i;j<=n;j+=i)s[j]=false;}
  for(i=2;i<=n;i++)if(s[i])sum+=i;
  cout<<sum<<endl;
} 

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/algoritmy/23949

Ссылки в тексте:

[1] топик о старте соревнования: http://habrahabr.ru/post/164515/

[2] shadeware: http://habrahabr.ru/users/shadeware/

[3] mikhaelkh: http://habrahabr.ru/users/mikhaelkh/

[4] Icemore: http://habrahabr.ru/users/icemore/

[5] ripatti: http://habrahabr.ru/users/ripatti/

[6] kbxxi: http://habrahabr.ru/users/kbxxi/

[7] monoid: http://habrahabr.ru/users/monoid/

[8] Zver1992: http://habrahabr.ru/users/zver1992/

[9] Mrrl: http://habrahabr.ru/users/mrrl/

[10] Staker: http://habrahabr.ru/users/staker/

[11] SyDr: http://habrahabr.ru/users/sydr/

[12] vbarinov: http://habrahabr.ru/users/vbarinov/

[13] vanla: http://habrahabr.ru/users/vanla/

[14] MaSaK: http://habrahabr.ru/users/masak/

[15] dark1ight: http://habrahabr.ru/users/dark1ight/

[16] udalov: http://habrahabr.ru/users/udalov/

[17] bklim: http://habrahabr.ru/users/bklim/

[18] cfighter: http://habrahabr.ru/users/cfighter/

[19] VladVR: http://habrahabr.ru/users/vladvr/

[20] borozdinKirill: http://habrahabr.ru/users/borozdinkirill/

[21] ZhekSooN: http://habrahabr.ru/users/zheksoon/

[22] madkite: http://habrahabr.ru/users/madkite/

[23] akazakow: http://habrahabr.ru/users/akazakow/

[24] mingrief: http://habrahabr.ru/users/mingrief/

[25] pasky: http://habrahabr.ru/users/pasky/

[26] ewnd9: http://habrahabr.ru/users/ewnd9/

[27] gnhdnb: http://habrahabr.ru/users/gnhdnb/

[28] through_horizon: http://habrahabr.ru/users/through_horizon/

[29] kosmos89: http://habrahabr.ru/users/kosmos89/

[30] Nickel: http://habrahabr.ru/users/nickel/

[31] infsega: http://habrahabr.ru/users/infsega/

[32] shuternay: http://habrahabr.ru/users/shuternay/

[33] smyatkin_maxim: http://habrahabr.ru/users/smyatkin_maxim/

[34] azhi: http://habrahabr.ru/users/azhi/

[35] Valmount: http://habrahabr.ru/users/valmount/

[36] Alick09: http://habrahabr.ru/users/alick09/

[37] alexeibs: http://habrahabr.ru/users/alexeibs/

[38] DoctorStein: http://habrahabr.ru/users/doctorstein/

[39] Kenny_HORROR: http://habrahabr.ru/users/kenny_horror/

[40] Ratio2: http://habrahabr.ru/users/ratio2/

[41] mobi: http://habrahabr.ru/users/mobi/

[42] Lonsdaleite: http://habrahabr.ru/users/lonsdaleite/

[43] tiirz: http://habrahabr.ru/users/tiirz/

[44] Goryn: http://habrahabr.ru/users/goryn/

[45] Leronxp: http://habrahabr.ru/users/leronxp/

[46] singstio: http://habrahabr.ru/users/singstio/

[47] CTAKAH4uK: http://habrahabr.ru/users/ctakah4uk/

[48] XMypuK: http://habrahabr.ru/users/xmypuk/

[49] Edelweiss: http://habrahabr.ru/users/edelweiss/

[50] Jovfer: http://habrahabr.ru/users/jovfer/

[51] crimaniak: http://habrahabr.ru/users/crimaniak/

[52] luckman: http://habrahabr.ru/users/luckman/

[53] ladilova: http://habrahabr.ru/users/ladilova/

[54] Gromilo: http://habrahabr.ru/users/gromilo/

[55] FreeCoder: http://habrahabr.ru/users/freecoder/

[56] awa: http://habrahabr.ru/users/awa/

[57] sprosin: http://habrahabr.ru/users/sprosin/

[58] BelerafonL: http://habrahabr.ru/users/belerafonl/

[59] polar_winter: http://habrahabr.ru/users/polar_winter/

[60] luckychess: http://habrahabr.ru/users/luckychess/

[61] darinflar: http://habrahabr.ru/users/darinflar/

[62] kreep: http://habrahabr.ru/users/kreep/

[63] iqmaker: http://habrahabr.ru/users/iqmaker/

[64] dima11221122: http://habrahabr.ru/users/dima11221122/

[65] kos66: http://habrahabr.ru/users/kos66/

[66] alex_r: http://habrahabr.ru/users/alex_r/

[67] dannk: http://habrahabr.ru/users/dannk/

[68] andreybotanic: http://habrahabr.ru/users/andreybotanic/

[69] realsugar: http://habrahabr.ru/users/realsugar/

[70] kromych: http://habrahabr.ru/users/kromych/

[71] iamnp: http://habrahabr.ru/users/iamnp/

[72] skripkakos: http://habrahabr.ru/users/skripkakos/

[73] OnScript: http://habrahabr.ru/users/onscript/

[74] aserty: http://habrahabr.ru/users/aserty/

[75] ivanbl4: http://habrahabr.ru/users/ivanbl4/

[76] kinbote: http://habrahabr.ru/users/kinbote/

[77] ryokuyou: http://habrahabr.ru/users/ryokuyou/

[78] quarck: http://habrahabr.ru/users/quarck/

[79] sultanko: http://habrahabr.ru/users/sultanko/

[80] Yura1111: http://habrahabr.ru/users/yura1111/

[81] Troyal: http://habrahabr.ru/users/troyal/

[82] Izobara: http://habrahabr.ru/users/izobara/

[83] PutPixel: http://habrahabr.ru/users/putpixel/

[84] CheshaNeko: http://habrahabr.ru/users/cheshaneko/

[85] fromnull: http://habrahabr.ru/users/fromnull/

[86] ronsenval: http://habrahabr.ru/users/ronsenval/

[87] undiabler: http://habrahabr.ru/users/undiabler/

[88] MrDindows: http://habrahabr.ru/users/mrdindows/

[89] kladov: http://habrahabr.ru/users/kladov/

[90] Andrew146: http://habrahabr.ru/users/andrew146/

[91] vaux: http://habrahabr.ru/users/vaux/

[92] marsencpp: http://habrahabr.ru/users/marsencpp/

[93] phrk: http://habrahabr.ru/users/phrk/

[94] burtsev: http://habrahabr.ru/users/burtsev/

[95] yooll: http://habrahabr.ru/users/yooll/

[96] DarkContact: http://habrahabr.ru/users/darkcontact/

[97] drongosar: http://habrahabr.ru/users/drongosar/

[98] alexvab: http://habrahabr.ru/users/alexvab/

[99] MrKonshyn: http://habrahabr.ru/users/mrkonshyn/

[100] appplemac: http://habrahabr.ru/users/appplemac/

[101] msn92: http://habrahabr.ru/users/msn92/

[102] ikalnitsky: http://habrahabr.ru/users/ikalnitsky/

[103] 0Chekhov0: http://habrahabr.ru/users/0chekhov0/

[104] savik1: http://habrahabr.ru/users/savik1/

[105] zenden2k: http://habrahabr.ru/users/zenden2k/

[106] alexaol: http://habrahabr.ru/users/alexaol/

[107] Avitella: http://habrahabr.ru/users/avitella/

[108] yrik04: http://habrahabr.ru/users/yrik04/

[109] topz: http://habrahabr.ru/users/topz/

[110] drozdVadym: http://habrahabr.ru/users/drozdvadym/

[111] anton280: http://habrahabr.ru/users/anton280/

[112] ehead01: http://habrahabr.ru/users/ehead01/

[113] 8086: http://habrahabr.ru/users/8086/

[114] DIMKAAAAA: http://habrahabr.ru/users/dimkaaaaa/

[115] mike_4d: http://habrahabr.ru/users/mike_4d/

[116] alineman: http://habrahabr.ru/users/alineman/

[117] pavor84: http://habrahabr.ru/users/pavor84/

[118] denzp: http://habrahabr.ru/users/denzp/

[119] RamTararam: http://habrahabr.ru/users/ramtararam/

[120] DezzK: http://habrahabr.ru/users/dezzk/

[121] frozendog: http://habrahabr.ru/users/frozendog/

[122] sasha237: http://habrahabr.ru/users/sasha237/

[123] aX1v: http://habrahabr.ru/users/ax1v/

[124] rutigl: http://habrahabr.ru/users/rutigl/

[125] Joric: http://habrahabr.ru/users/joric/

[126] LibertyPaul: http://habrahabr.ru/users/libertypaul/

[127] volokitinss: http://habrahabr.ru/users/volokitinss/

[128] Formicidae: http://habrahabr.ru/users/formicidae/

[129] fao: http://habrahabr.ru/users/fao/

[130] vkm: http://habrahabr.ru/users/vkm/

[131] kleninz: http://habrahabr.ru/users/kleninz/

[132] knstqq: http://habrahabr.ru/users/knstqq/

[133] morphing: http://habrahabr.ru/users/morphing/

[134] Vaddddd: http://habrahabr.ru/users/vaddddd/

[135] ancalled: http://habrahabr.ru/users/ancalled/

[136] fasterthanlight: http://habrahabr.ru/users/fasterthanlight/

[137] sinc: http://habrahabr.ru/users/sinc/

[138] Satayev: http://habrahabr.ru/users/satayev/

[139] eversyt: http://habrahabr.ru/users/eversyt/

[140] zyss: http://habrahabr.ru/users/zyss/

[141] smile616: http://habrahabr.ru/users/smile616/

[142] Moress: http://habrahabr.ru/users/moress/

[143] zzzeeerrr0: http://habrahabr.ru/users/zzzeeerrr0/

[144] kilotaras: http://habrahabr.ru/users/kilotaras/

[145] I_AM_FAKE: http://habrahabr.ru/users/i_am_fake/

[146] Aksiom: http://habrahabr.ru/users/aksiom/

[147] WarAngel_alk: http://habrahabr.ru/users/warangel_alk/

[148] skovpen: http://habrahabr.ru/users/skovpen/

[149] safinaskar: http://habrahabr.ru/users/safinaskar/

[150] jit_md: http://habrahabr.ru/users/jit_md/

[151] mrigi: http://habrahabr.ru/users/mrigi/

[152] Tweekaz: http://habrahabr.ru/users/tweekaz/

[153] Thunderbird: http://habrahabr.ru/users/thunderbird/

[154] shock_one: http://habrahabr.ru/users/shock_one/

[155] shy: http://habrahabr.ru/users/shy/

[156] Dgut: http://habrahabr.ru/users/dgut/

[157] ShouldNotSeeMe: http://habrahabr.ru/users/shouldnotseeme/

[158] therussianphysicist: http://habrahabr.ru/users/therussianphysicist/

[159] aamuvirkku: http://habrahabr.ru/users/aamuvirkku/

[160] IntegralUnderground: http://habrahabr.ru/users/integralunderground/

[161] 0leksandr: http://habrahabr.ru/users/0leksandr/

[162] ipoder: http://habrahabr.ru/users/ipoder/

[163] IharBury: http://habrahabr.ru/users/iharbury/

[164] xtern: http://habrahabr.ru/users/xtern/

[165] KycokCo6aku: http://habrahabr.ru/users/kycokco6aku/

[166] gridem: http://habrahabr.ru/users/gridem/

[167] minc2319: http://habrahabr.ru/users/minc2319/

[168] okneigres: http://habrahabr.ru/users/okneigres/

[169] antidotcb: http://habrahabr.ru/users/antidotcb/

[170] merkius: http://habrahabr.ru/users/merkius/

[171] iTwin: http://habrahabr.ru/users/itwin/

[172] bstructure: http://habrahabr.ru/users/bstructure/

[173] fsv: http://habrahabr.ru/users/fsv/

[174] 411: http://habrahabr.ru/users/411/

[175] pleha: http://habrahabr.ru/users/pleha/

[176] staricam: http://habrahabr.ru/users/staricam/

[177] chipa: http://habrahabr.ru/users/chipa/

[178] dosefose: http://habrahabr.ru/users/dosefose/

[179] SergeySib: http://habrahabr.ru/users/sergeysib/

[180] Ptax: http://habrahabr.ru/users/ptax/

[181] можно тут: http://3.14.by/files/compilation_results.zip

[182] Войдите: https://www.pvsm.ru/login/

[183] Источник: http://habrahabr.ru/post/164567/

Нажмите здесь для печати.