【Luogu1072】Hankson的趣味题

Source and Judge

NOIP2009 提高组 T2
Luogu1072
Caioj1538

Problem

【Brief description】
已知正整数 a0,a1,b0,b1,正整数 x 满足:
1. gcd(x,a0)=a1
2. lcm(x,b0)=b1
求x的个数
【Input】
第一行为一个正整数 n,表示有 n 组输入数据。
接下来的 n 行每行一组输入数据,为四个正整数 a0,a1,b0,b1,每两个整数之间用一个空格隔开。
【Output】
共 n 行。每组输入数据的输出结果占一行,为一个整数。
对于每组数据:
若不存在这样的 x,请输出 0;
若存在这样的 x,请输出满足条件的 x 的个数;
【Limited conditions】
输入数据保证 a0 能被 a1 整除,b1 能被 b0 整除。
对于 50%的数据,保证有 1≤a0,a1,b0,b1≤10000 且 n≤100。
对于 100%的数据,保证有 1≤a0,a1,b0,b1≤2,000,000,000 且 n≤2000。
【Sample input】
2
41 1 96 288
95 1 37 1776
【Sample output】
6
2
【Sample explanation】
第一组输入数据,x 可以是 9、18、36、72、144、288,共有 6 个。
第二组输入数据,x 可以是 48、1776,共有 2 个。

Record

1h

Analysis1

请先思考后再展开

优雅的暴力:
观察柿子,不难发现x是a1的倍数,b1的约数
枚举b1约数即x,验证即可

时间复杂度:最坏$O(n*sqrt(b1)*log2(b1))$
极限26亿,然鹅luogu上还是很快的

Code1

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
//*******************全局常量*******************
const int MAXN=150;
//*******************全局定义*******************
//*******************实现*******************
int gcd(int x,int y) {return (y==0)?x:gcd(y,x%y);}
//*******************主函数*******************
int main()
{
int n;scanf("%d",&n);
while(n--)
{
int a0,a1,b0,b1;scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
int ans=0;
for(int x=1;x*x<=b1;x++)
{
if(b1%x==0 and x%a1==0 and gcd(x,a0)==a1 and gcd(x,b0)*b1==x*b0) ++ans;
int tx=b1/x;
if(tx!=x and b1%tx==0 and tx%a1==0 and gcd(tx,a0)==a1 and gcd(tx,b0)*b1==tx*b0) ++ans;
}
printf("%d\n",ans);
}
}

Analysis2

请先思考后再展开

虽然过去了,显然跑得很慢呀

UP 2018.8.6:
讲讲正解吧为了方便,改改字母
gcd(x,a)=c
lcm(x,b)=d

先从优化的角度反思上面的做法,我们可以把暴力判断gcd消耗的log省去
具体做法是,从质因数p的层面上考虑gcd和lcm,那么就变成了次幂的min和max
也就是说,枚举约数质因数p,设其在a,b,c,d,x中次幂数分别是ma,mb,mc,md,mx
对于gcd:
①$ma=mc,mx>=mc$
②$ma>mc,mx=mc$
③$ma<mc,无解$
对于lcm:
①$mb=md,mx=md$
②$mb<md,mx=md$
③$mb>md,无解$

合并情况如下:
①$ma=mc,mb=md,mc<=md,则mc<=mx<=md$,共md-mc+1种
②$ma=mc,mb<md,mc<=md,则mx=md$,共1种
③$ma>mc,mb=md,mc<=md,则mx=mc$,共1种
④$ma>mc,mb<md,mc=md,则mx=mc=md$,共1种
⑤其他,无解

最后把每种p下,mx可行的选择数乘法原理即可
把质数预处理一下,然后根据分布数量
这样的复杂度是$O(n \times \sqrt d / log_2( \sqrt d) )$

Code2

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
const int MAXNUM=50000;
int prime[MAXNUM],pr=0;
bool v[MAXNUM];
void pre()
{
for(int i=2;i<MAXNUM;i++)
{
if(!v[i]) prime[++pr]=i;
for(int j=1;j<=pr and ll(i)*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int a,b,c,d;
int ans;
void solve(int prm)
{
int ma=0;while(a%prm==0) ma++,a/=prm;
int mb=0;while(b%prm==0) mb++,b/=prm;
int mc=0;while(c%prm==0) mc++,c/=prm;
int md=0;while(d%prm==0) md++,d/=prm;
if(ma==mc and mb==md and mc<=md) ans*=md-mc+1;
else if(ma==mc and mb<md and mc<=md) ;
else if(ma>mc and mb==md and mc<=md) ;
else if(ma>mc and mb<md and mc==md) ;
else ans=0;
}
int main()
{
pre();
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&a,&c,&b,&d);
ans=1;
for(int i=1;i<=pr;i++) if(d%prime[i]==0) solve(prime[i]);
if(d>1) solve(d);//剩下的唯一质因数
printf("%d\n",ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/7398.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%