ACM暴力解题题解（二）

1.1218-XTUOJ

考点：数学公式，素数的判断方法

思路分析：

      审题，题目的意思很明确，求一个数有多少个因子。首先我们用暴力解题，但这里要注意，用for循环，判断给定数值num能整除的数字，其循环的最大值为sqrt(num),当num不是平方数时，每检测到一个数值，count加2,因为检测到一个数字可以被整除，那么必定存在另一个可以被整除的数字，num是平方数，且检测到了sqrt(num)时，count加1。代码提交后，发现超时，那么我们要在原算法的基础上加以修改。该题目用到了如下数学公式：对于任意的整数N，分解质因数得到N= P1^x1 * P2^x2* …… * Pn^xn; 则N的因子个数M为 M=（x1+1） * （x2+1） * …… *（xn+1）;注：P1,P2....等都为质数。

      那么有了这个数学公式，我们要怎么下手呢？本着从特殊到一般的思路，6=2X3，6的因子个数N（6）=2X2=4，那么实质上，我们就是要得出每个因子的幂值，2的幂值怎么得？经过分析，只要6整除2一直到不能在整除，那么我们就得出了2的幂值，然后把最后的出数对3进行同样的操作即可。至此我们已经把这个题目解析了一半。

      接下来，还有最后一个问题，对于任意数，我们怎么办？由暴力解题的规律我们可以知道，一个非素数的数，它会有一半的因子在sqrt(num)之前，那么，我们以这个为切入点，利用for循环，在sqrt(num)之前，找到可以整除的因子及其幂，但是我们可以发现这样的算法的时间复杂度好像没有什么变化，那么在此基础上我们还要怎么改进呢？我们发现，其实num的值在算法执行的过程中一直在改变，我们也一直在找num的因子，那么for循环i的上界是不是也应该改变一下呢？我们可以尝试一下。试验后发现，这样的算法对于质数好像不适用，因为num在sqrt(num)之前没有可以除的数，如：7=7，在这种情况下，我们是不是可以判定num剩余到最后的数一定为一个质数呢？

      思考到这里，我们就可以在最后就一个num是否等于1的判断，试验后发现，accepted。

易错：注意数据精度。

扩展：

如何理解，"对于一个自然数n，如果n在sqrt(n)之前没有因子的话，那么在sqrt(n)之后也没有因子"这个规律呢？

解：

设f(x)=n/x，其中n，x均为整数。

如果1<=x<=sqrt(n)，则sqrt(n)<=f(x)<=n。

由题目假设可知，当1<=x<=sqrt(n)，f(x)均不为整数，证明当sqrt(n)=<x<=n，f(x)均不为整数。

证明：设任意1=<a<=sqrt(n)，且a为整数，b=n/a，由题可知b不为整数。a=n/b。

那么对于sqrt(n)=<x<=n，x为整数，1<=f(x)<=sqrt(n)，假设f(x)为整数，由上述条件知，对于a=n/b，a为1<=a<=sqrt(n)任意整数，b不为整数，但对于sqrt(n)=<x<=n，f(x)=n/x，f(x)为整数，而且x也为整数，这和已知条件矛盾，所以综上，由反证法可知，结论成立.。

题目描述

小明一天在做a+b时，突然他想知道a+b能被哪些数整除了？比如说2+4=6，能整除6的数有1,2,3,6，一共4个。 请你帮他算一下，a+b的和能被几个数整除。

输入

第一行是一个整数K，表示样例的个数。 每个样例占一行，为两个整数a，b，(1≤a,b≤1e9)。

输出

每行输出一个样例的结果，为一个整数。

样例输入

2
2 3
4 2

样例输出

2
4

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 1000
int A[MAX];
int main()
{
    int a,b,sum;
    int K;
    scanf("%d",&K);
    while(K--)
    {
        int result=1;
        scanf("%d%d",&a,&b);
        sum=a+b;
        for(int i=2;i*i<=sum;i++)//找出sum的因子所对应的幂,sum的值一直在变化
        {
            if(sum%i==0)
            {
                int count=0;
                while(sum%i==0)
                {
                    count++;
                    sum=sum/i;
                }
                result*=(count+1);//在得出后直接计算
                if(sum==1) break;
            }
        }
        if(sum!=1) result*=2;//最后还留下一个质数的话，还加乘以2
        printf("%d\n",result);
    }
    return 0;
}

2.1178-XTUOJ

考点：数学问题

易错：

(1)利用长度解题时，要注意数据类型int/double。矩形对角线坐标有多种情况，必须注意到。

(2)谨慎使用全局变量，如果一定要用，那么请注意全局变量的命名。请看下面的例子：

      当使用上面这个代码的时候，编译器不会报错，但是OJ上却会显示compile error。因为在头文件中定义了很多变量，难免会有全局变量和头文件中的变量重名的情况出现，所以OJ上才会显示compile error 。

解决方法有两种：

（1）将全局变量的变量名改得复杂一点。

#include<bits/stdc++.h>
using namespace std;
int x1_xx,y1_xx,x2_xx,y2_xx;
int x3_xx,y3_xx,x4_xx,y4_xx;

int main()
{
    int K;
    scanf("%d",&K);
    while(K--)
    {
        scanf("%d %d %d %d",&x1_xx,&y1_xx,&x2_xx,&y2_xx);
        scanf("%d %d %d %d",&x3_xx,&y3_xx,&x4_xx,&y4_xx);
        double D1_x=(x1_xx+x2_xx)/2;//第一个矩形重心横坐标
        double D1_y=(y1_xx+y2_xx)/2;//第一个矩形重心纵坐标
        double D2_x=(x3_xx+x4_xx)/2;
        double D2_y=(y3_xx+y4_xx)/2;
        double D_line=(abs(x1_xx-x2_xx)+abs(x3_xx-x4_xx))/2;
        double D_colum=(abs(y1_xx-y2_xx)+abs(y3_xx-y4_xx))/2;
        if(fabs(D1_x-D2_x)<D_line&&fabs(D1_y-D2_y)<D_colum) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

（2）将全局变量改为局部变量。

分析：

法一：

      我们还是从解题的一般步骤出发，题目意思很简单，给定两个矩形，判断它们是否相交。我们根据特殊到一般的思路，先画一个简单的矩形看看。如

矩形一：（0，0） （1，1）

矩形二：（0，0） （2，2）

这两个矩形是相交的，那么相交还有哪些情况呢？我们开始一一列举，如下图所示。

       图中一共表现出了两种元素，一个是线段，一个是点，分别对应着，长度和坐标（其实还有向量）。我们先从坐标出发，找找看这些相交情况有什么特征。因为给定的矩形坐标有很多种情况，如果不控制变量分析，我们的问题将很难继续分析下去，我们假定给定的矩形坐标:

第一个：x1,y1,x2,y2;（x1<x2&&y1<y2）

第二个：x3,y3,x4,y4;（x3<x4&&y3<y4）（问题如果十分难解决，不妨把给定条件增多，然后继续思考）

限定以后，我们找找看可以发现，相交所形成的矩形坐标:

r1_x=max(x1,x3);

r1_y=max(y1,y3);

r2_x=min(x2,x4);

r2_y=min(y2,y4);

而且有r1_x<r2_x&&r1_y<r2_y，至此，这个问题就已经解决一半了。

那么我们自己给定的条件要怎么办呢，经过思考，我们只要写一个函数把给定坐标变换一下即可。

法二：

我们上面还提到了，图中还体现出了一个元素长度，那么我们从长度入手，通过画图还有如下规律：

double D1_x=(x1+x2)/2;//第一个矩形重心横坐标
double D1_y=(y1+y2)/2;//第二个矩形重心纵坐标

两个矩形的重心在x轴上的投影，他们之间的距离小于两个矩形的边在x轴上投影的长度和的一半，而且还必须有

两个矩形的重心在y轴上的投影，他们之间的距离小于两个矩形的边在y轴上投影的长度和的一半。

题目描述

给你两个平行于坐标轴的矩形，请判断两者是不是相交（面积有重合的部分）？

输入

第一行是一个整数K，表示样例数。 每个样例占两行，每行是4个整数，表示一个矩形的对角线点的坐标，坐标值为0到1,000之间。

输出

每个样例输出一个结果，相交输出Yes，否则输出No。

样例输入

2
0 0 1 1
1 1 2 2
0 0 2 2
1 1 3 3

样例输出

No
Yes

代码如下：

解法1：

#include<bits/stdc++.h>
using namespace std;


void MatrixChange(int &x1,int &y1,int &x2,int &y2)//坐标变换一下
{
    if(x1<x2&&y1<y2) return;
        else if(x2<x1&&y2<y1)
    {
        int t=x2;
        x2=x1;
        x1=t;
        t=y2;
        y2=y1;
        y1=t;
    }
    else if(x1<x2&&y1>y2)
    {
        int t=y2;
        y2=y1;
        y1=t;
    }
    else if(x1>x2&&y1<y2)
    {
        int t=x2;
        x2=x1;
        x1=t;
    }
}

int main()
{
    int x1,y1,x2,y2;
    int x3,y3,x4,y4;
    int K;
    scanf("%d",&K);
    while(K--)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        scanf("%d %d %d %d",&x3,&y3,&x4,&y4);
        MatrixChange(x1,y1,x2,y2);
        MatrixChange(x3,y3,x4,y4);
        int r1_x=max(x1,x3);
        int r1_y=max(y1,y3);
        int r2_x=min(x2,x4);
        int r2_y=min(y2,y4);
        if(r1_x<r2_x&&r1_y<r2_y) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

解法二：

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int K;
    scanf("%d",&K);
    while(K--)
    {
        int x1,y1,x2,y2;
        int x3,y3,x4,y4;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        scanf("%d %d %d %d",&x3,&y3,&x4,&y4);
        double D1_x=(x1+x2)/2;//第一个矩形重心横坐标
        double D1_y=(y1+y2)/2;//第二个矩形重心纵坐标
        double D2_x=(x3+x4)/2;
        double D2_y=(y3+y4)/2;
        double D_line=(abs(x1-x2)+abs(x3-x4))/2;
        double D_colum=(abs(y1-y2)+abs(y3-y4))/2;
        if(fabs(D1_x-D2_x)<D_line&&fabs(D1_y-D2_y)<D_colum) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}