洛谷P1072 Hankson 的趣味题(题解)

https://www.luogu.org/problemnew/show/P1072(题目传送)

数学的推理在编程的体现越来越明显了。(本人嘀咕)

首先,我们知道这两个等式: (a0,x)=a1,[b0,x]=b1(a0,x)=a1,[b0,x]=b1

于是,我们可以设: x=a1*p,b1=x*tx=a1∗p,b1=x∗t

于是有: a1*p*t=b1a1∗p∗t=b1

所以我们令: b1/a1=sb1/a1=s

则: p*t=sp∗t=s

即: t=s/pt=s/p

又由最大公约数与最小公倍数的定义与性质可得:

(a0/a1,p)=1,(b1/b0,t)=1(a0/a1,p)=1,(b1/b0,t)=1

所以我们令: a0/a1=m,b1/b0=na0/a1=m,b1/b0=n

则有: (p,m)=1,(s/p,n)=1(p,m)=1,(s/p,n)=1

这就是第一个结论,我们称其为结论一。事实上,我们其实已经可以由结论一整理出可以AC的方法,即用sqrt(s)的复杂度枚举s的因数,然后将每个因数放到结论一中,看看是否成立,再统计所有符合结论一的因数的个数,然后输出即可。这种算法的复杂度是:O(sqrt(s)*log(s)*n)。这样其实也能卡过数据,但是还是没有达到理论上的通过。所以我们还要继续优化。

我们考虑(s/p,n)=1。如果s/p与n有相同质因数,则无法使(s/p,n)=1成立。于是,为了使(s/p,n)=1成立,我们可以将s与n所有相同的质因数从s中去掉(不动s/p的原因是s/p是s的因变量,改变无意义),得到剩余的数l,若(s/p,n)=1成立,s/p就必须是l的约数。

我们继续考虑(p,m)=1。因为s/p是l的约数,那么p就一定可以表示为这样的形式:

p=(s/l)*r(因为s/p*r=p,r属于N*

即:p一定是s/l的倍数(因为s/p是l的约数),r也是l的约数。于是就又有:

r|l,且(r,m)=1

这就是第二个结论,我们称其为结论二。而解决结论二的方法便很明显了。我们可以用与解决结论一相似的方法,将l与m所有相同的质因数从l中去掉,得到剩余的数q。那么所有使结论二成立的r都是q的因数了。然后,我们可以用sqrt(q)的复杂度枚举q的所有因数,输出q的因数个数就行了。这样,复杂度便降到了:O((sqrt(s)+log(s))*n),从理论来说也不会超时了。

还有一点需要注意,那就是特判没有符合要求的x的情况。这种情况出现只有四种可能:

1、s不为整数

2、m不为整数

3、n不为整数

4、(s/l,m)≠1,即因为p是s/l的倍数,所以无论r取何值,都会有(p,m)≠1

加上这四个特判,这道题便做完了。(来个总结公式:结论成立=筛去必要条件的不足+必要条件,这也算是一种思路吧)

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<string>
 7 using namespace std;
 8 int ssqrt;
 9 int cf(int a,int b)//去掉a中与b共有的质因数。思想:将b质因数分解,同时将a中与b共有的质因数去掉。
10 {
11     ssqrt=sqrt(b);
12     for(int i=2;i<=ssqrt;i++)//sqrt(b)复杂度质因数分解b
13     {
14         if(b%i==0)while(a%i==0)a/=i;//去掉a中与b共有的质因数,将a分解
15         while(b%i==0)b/=i;//将b质因数分解
16     }
17     if(b!=1)while(a%b==0)a/=b;//注意:此时b可能还不是1,因为b可能有比sqrt(b)更大的质因数,但至多只有一个,且它的次幂至多是1。所以如果b不是1,那就只能是一个质数。于是此时继续分解a。
18     return a;//返回剩下的a
19 }
20 int gcd(int a,int b){return b==0?a:gcd(b,a%b);}//辗转相除求最大公约数
21 int main()
22 {
23     int a0,a1,b0,b1;
24     int gs;
25     int m,n,s,l,q;
26     scanf("%d",&gs);
27     int cnt;
28     while(gs--)
29     {
30         scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
31         if(a0%a1|b1%b0|b1%a1){printf("0
");continue;}//如果m、n、s中有小数,则直接输出0。这里的代码用到了一些位运算
32         m=a0/a1,n=b1/b0,s=b1/a1;l=cf(s,n);//求出m、n、s,然后求出l
33         if(gcd(max(s/l,m),min(s/l,m))!=1){printf("0
");continue;}//如果不互质,则直接输出0
34         q=cf(l,m);cnt=0,ssqrt=sqrt(q);//求出q,开始枚举q的因数,求出q的因数个数
35         for(int i=1;i<=ssqrt;i++)if(q%i==0)cnt+=i==q/i?1:2;//这里注意,如果i==q/i,则只加1,否则加2
36         printf("%d
",cnt);//输出
37     }
38     return 0;

另附应用结论一的代码(好像更快。。。估计上面代码cf函数拖时间了吧):

 1 #include<cstdio>
 2 using namespace std;
 3 int gcd(int a,int b) {
 4     return b==0?a:gcd(b,a%b);
 5 }
 6 int main() {
 7     int T;
 8     scanf("%d",&T);
 9     while(T--) {
10         int a0,a1,b0,b1;
11         scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
12         int p=a0/a1,q=b1/b0,ans=0;
13         for(int x=1;x*x<=b1;x++) //精华
14             if(b1%x==0){
15                 if(x%a1==0&&gcd(x/a1,p)==1&&gcd(q,b1/x)==1) ans++;
16                 int y=b1/x;//得到另一个因子
17                 if(x==y) continue; 
18                 if(y%a1==0&&gcd(y/a1,p)==1&&gcd(q,b1/y)==1) ans++;
19             }
20         printf("%d
",ans);
21     }
22     return 0;
23 }

做题在纸上推理推理写写思路,更清晰地解题


给看到这里的OIer一个小干货吧(虽然很可能知道,但也是试了好久才总结出来的啊):cmd的窗口默认保存297行,宽80字符,高25字符

原文地址:https://www.cnblogs.com/InductiveSorting-QYF/p/10598817.html