关于去年的第二题..~~~
是数论吧..~~
搜索+剪枝只能80...
哪位高手能来讲讲..`~~...
NOI高手来...关于去年的NOIP第二题.
答案:3 悬赏:50 手机版
解决时间 2021-06-01 20:37
- 提问者网友：火车头
- 2021-06-01 12:08
最佳答案
- 五星知识达人网友：千杯敬自由
- 2021-06-01 12:35
我就是传说中的高手····
全部回答
- 1楼网友：第四晚心情
- 2021-06-01 13:30
思路1：
根据最大公约数的定义，X必定为最大公约数的倍数，那么我们可以去枚举a1的倍数，然后去验证最大公约数和最小公倍数是否符合条件。期待分数：50。
程序1：
var
a0,a1,b0,b1,i,j,n,k,x,tot:longint;
function gcd(a,b:longint):longint;
begin
if b=0 then exit(a) else exit(gcd(b,a mod b));
end;
begin
readln(n);
for k:=1 to n do
begin
tot:=0;
readln(a0,a1,b0,b1);
for i:=1 to (b1 div a1) do
begin
x:=i*a1;
if b1 mod x=0 then
if gcd(a0,x)=a1 then
if (b0*x) div (gcd(b0,x))=b1 then begin inc(tot); end;
end;
writeln(tot);
end;
end.
思路2：
根据最小公倍数和最大公约数分解质因数指数的特殊关系进行优化。比如两个数，分解质因数可以得到以下的式子
A=p1^a1+p2^a2+p3^a3……
B=p1^b1+p2^b2+p3^a3……
例如6和21就可以分解成
6=2^1+3^1+5^0+7^0……
21=2^0+3^1+5^0+7^1……
则最大公约数=2^(min(a1,b1))+3^(min(a2,b2))+5^(min(a3,b3))+7^(min(a4,b4))…
最小公倍数=2^(max(a1,b1))+3^(max(a2,b2))+5^(max(a3,b3))+7^(max(a4,b4))…
那么我们可以先将b1分解质因数，在根据最大公约数和最小公倍数在指数上的关系，进行搜索。期待分数：100
程序2：
var
p,x,c:array[0..1000] of longint;
a0,a1,b0,b1,i,j,k,m,tot,t,n:longint;
function gcd(a,b:longint):longint;
begin
if b=0 then exit(a) else exit(gcd(b,a mod b));
end;
procedure dfs(i,sum:longint);
var
max,j:longint;
begin
if i>m then
begin
inc(tot);
p[tot]:=sum;
exit;
end;
max:=sum;
dfs(i+1,max);
for j:=1 to c[i] do
begin
max:=max*x[i];
dfs(i+1,max);
end;
end;
procedure work(b:longint);
var i,p:longint;
begin
i:=2;
p:=b;
while i<=sqrt(p) do
begin
if p mod i=0 then
begin
inc(m);
x[m]:=i;
c[m]:=0;
repeat
inc(c[m]);
p:=p div i;
until p mod i<>0;
end;
inc(i);
end;
if p<>1 then
begin
inc(m);
x[m]:=p;
c[m]:=1;
end;
dfs(1,1);
end;
begin
readln(n);
for i:=1 to n do
begin
readln(a0,a1,b0,b1);
fillchar(p,sizeof(p),0);
fillchar(x,sizeof(x),0);
fillchar(c,sizeof(c),0);
m:=0;
tot:=0;
t:=0;
work(b1);
for j:=1 to tot do
if (gcd(p[j],a0)=a1) and ((p[j] div gcd(p[j],b0) * b0)=b1) then inc(t);
writeln(t);
end;
end.
思路三：
和思路二有异曲同工之妙。我们可以先预处理trunc(sqrt(2000000000))以内的质数，然后每读入一组数据，初始答案ans=1,然后我们循环质数，看a0、a1、b0、b1里面有多少个该质数因子，并且将这四个数分别消去所有该质数因子。我们设求出来的该因子个数分别是t1、t2、t3、t4。如果数据合法，那么t1>=t2,t3<=t4。根据最大公约数和最小公倍数的定义，我们要求的数所拥有的该质因子个数s必须要同时满足以下限制条件：
若t1>t2,则s=t2
若t1=t2，则s>=t2
若t3<t4,则s=t4
若t3=t4，则s<=t4
这样，我们或者求出了s的范围，要么证明了不存在合法数字。如果s存在合法取值，我们就将ans乘上s的合法取值个数，否则直接输出0。
注意：如果循环结束后，a0>1或b1>1，那么此时a0或b1一定是超过我们枚举的数字范围的质数。这时我们特殊判断一下就行了。我们的时间复杂度是循环质数复杂度+分解因数复杂度。分解因数最坏是该数为2的若干次方，所以复杂度的上限是log(2000000000)，很小。最慢的点在0.3秒以内出解。
程序3
program son;
var i,j,k,l,m,n,p,q,l2,r2,r,s,t,a0,a1,b0,b1,ans:longint;
prime:array[0..60000] of longint;
need:array[0..60000] of longint;
pd:boolean;
function pri(x:longint):boolean;
var g:longint;
begin
for g:=2 to trunc(sqrt(x)) do
if x mod g=0 then exit(false);
exit(true);
end;
begin
p:=1;prime[1]:=2;
for i:=3 to 50000 do if pri(i) then
begin
inc(p);
prime[p]:=i;
end;
read(n);
for t:=1 to n do
begin
read(a0,a1,b0,b1);
ans:=1;
fillchar(need,sizeof(need),255);
q:=p;
pd:=true;
for i:=1 to p do
begin
l:=0;r:=0;l2:=0;r2:=0;
while a0 mod prime[i]=0 do
begin
inc(l);a0:=a0 div prime[i];
end;
while a1 mod prime[i]=0 do
begin
inc(r);a1:=a1 div prime[i];
end;
while b0 mod prime[i]=0 do
begin
inc(l2);b0:=b0 div prime[i];
end;
while b1 mod prime[i]=0 do
begin
inc(r2);b1:=b1 div prime[i];
end;
if l>r then need[i]:=r;
if l2<r2 then
begin
if (need[i]>-1)and(need[i]<>r2) then
begin
pd:=false;break;
end;
need[i]:=r2;
end;
if need[i]=-1 then
if r2<r then
begin
pd:=false;break;
end else ans:=ans*(r2-r+1);
end;
if i=p then
if a0>1 then
begin
inc(i);prime[i]:=a0;
l:=0;r:=0;l2:=0;r2:=0;
while a0 mod prime[i]=0 do
begin
inc(l);a0:=a0 div prime[i];
end;
while a1 mod prime[i]=0 do
begin
inc(r);a1:=a1 div prime[i];
end;
while b0 mod prime[i]=0 do
begin
inc(l2);b0:=b0 div prime[i];
end;
while b1 mod prime[i]=0 do
begin
inc(r2);b1:=b1 div prime[i];
end;
if l>r then need[i]:=r;
if l2<r2 then
begin
if (need[i]>-1)and(need[i]<>r2) then
begin
pd:=false;
end;
need[i]:=r2;
end;
if need[i]=-1 then
if r2<r then
begin
pd:=false;
end else ans:=ans*(r2-r+1);
dec(i);
end;
if i=p then
if b1>1 then
begin
inc(i);prime[i]:=b1;
l:=0;r:=0;l2:=0;r2:=0;
while a0 mod prime[i]=0 do
begin
inc(l);a0:=a0 div prime[i];
end;
while a1 mod prime[i]=0 do
begin
inc(r);a1:=a1 div prime[i];
end;
while b0 mod prime[i]=0 do
begin
inc(l2);b0:=b0 div prime[i];
end;
while b1 mod prime[i]=0 do
begin
inc(r2);b1:=b1 div prime[i];
end;
if l>r then need[i]:=r;
if l2<r2 then
begin
if (need[i]>-1)and(need[i]<>r2) then
begin
pd:=false;
end;
need[i]:=r2;
end;
if need[i]=-1 then
if r2<r then
begin
pd:=false;
end else ans:=ans*(r2-r+1);
dec(i);
end;
if not pd then writeln(0) else writeln(ans);
end;
end.
- 2楼网友：酒者煙囻
- 2021-06-01 13:18
【问题描述】
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A
市对
所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根
据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%
（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有
选手。
现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成
绩。
【输入】
输入文件名为
score.in。
第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其
中n
表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%
向下取整后小于等于n。
第二行到第 n+1
行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k
（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤
100）。数据保证选手的报名号各
不相同。
【输出】
输出文件
score.out。
第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为
进入面试的选手的实际人数。
从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手
的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的
顺序输出。
【输入输出样例】
score.in
score.out
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001
88
88 5
1005 95
2390 95
1000 90
1001 88
3239
88
【样例说明】
m*150% = 3*150% = 4.5，向下取整后为4。保证4
个人进入面试的分数线为88，但因为88
有重分，所以所有成绩大于等于88 的选手都可以进入面试，故最终有5 个人进入面试。
type
rec=record
num:longint;
grade:longint;
end;
arraytype=array[1..5100]
of rec;
procedure qsort(var a:arraytype;lx,rx:longint);
var
i,j:longint;
x,temp:rec;
begin
i:=lx;
j:=rx;
x:=a[random(j-i+1)+i];
while
i<=j do begin
while (a[i].grade>x.grade) or ((a[i].grade=x.grade) and
(a[i].num<x.num)) do inc(i);
while (a[j].grade<x.grade) or
((a[j].grade=x.grade) and (a[j].num>x.num)) do dec(j);
if i<=j then
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
inc(i);
dec(j);
end;
end;
if
i<rx then qsort(a,i,rx);
if j>lx then qsort(a,lx,j);
end;
var
a:arraytype;
n,m,i,luquxian,d:longint;
begin
assign(input,'score.in');
assign(output,'score.out');
reset(input);
rewrite(output);
read(n,m);
for
i:=1 to n do
read(a[i].num,a[i].grade);
qsort(a,1,n);
m:=trunc(m*3/2);
luquxian:=a[m].grade;
for
i:=1 to n do if a[i].grade>=luquxian then inc(d);
writeln(luquxian,'
',d);
for i:=1 to n do if a[i].grade>=luquxian then writeln(a[i].num,'
',a[i].grade);
close(input);
close(output);
end.
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯