首页 > 代码库 > NOIP模拟题——计数
NOIP模拟题——计数
【题目描述】
我们都爱奎奎，最近奎奎给大家出了一道题。
他告诉了我们一个n*m 的矩阵点，在这个矩阵中的点可以连接成很多线，求
长度等于某一长度的线的条数。
【输入】)
第一行三个正整数n,m,t，第2-t+1 行为所求Wi。
【输出】
输出1 行，共t 个数，第i 个数为满足长度Wi 的条数。
【输入样例1】
3 3 1
1
例如此为3*3 的矩阵点
【输出样例1】
12
【输入样例2】
7 11 1
5
【输出样例2】
168
【输入样例3】
3 5 1
2
【输出样例3】
14
【数据说明】
测试点数据范围
1 2 N<=2000;M<=2000;T<=100
3 4 N<=1000000;M<=1000000；T<=100
5 6 N<=10000000;M<=10000000；T<=100
7 8 N<=100000000;M<=100000000；T<=100
9 10 N<=1000000000;M<=1000000000；T<=100
W<=2max(n,m);
这道题就是找勾股数，但是太难想了。
先考虑直线水平和竖直的情况：
if(n>x)
ans+=(n-x)*m;
if(m>x)
ans+=(m-x)*n;
在考虑斜着的情况：
我们设要找的长度为r，则设x²+y²=r²
得到x=sqrt((r+y)*(r-y))
设d=gcd(r+y,r-y),A=(r-y)/d,B=(r+y)/d
得到x=d*sqrt(A*B)，推出A*B是完全平方数，又因为A，B是两数除以最大公因数
得出：A、B是互质的完全平方数
A+B=2*r/d得出(A+B)*d=2*r
枚举d从1~sqrt(2*r)、2*r%d=0(原因：若d大于根号2r后，相当于A+B的值和d的值颠倒，重复算了)
再枚举a从1~sqrt(r/d)——保证A<B，再判断B是否是完全平方数
若满足，联立A=(r-y)/d,B=(r+y)/d得：
y=(A-B)*d/2，通过r和y得出x
再算时间复杂度。枚举d用根号2*r，约5*1e4
再枚举1~根号r/d，应该大于100，再乘上100组数据，超时。
但为什么不超时？
因为d的取值不可能是到根号2*r，所以后面的循环次数也大幅降低了。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int n,m,t; 7 int gcd(int x,int y) 8 { 9 if(y==0)return x;10 return gcd(y,x%y);11 }12 int main()13 {14 freopen("amount.in","r",stdin);15 freopen("amount.out","w",stdout);16 scanf("%d%d%d",&n,&m,&t);17 if(n>m)swap(n,m);//n小 18 for(int j=1;j<=t;j++)19 {20 long long x;scanf("%I64d",&x);21 long long ans=0;22 if(n>x)23 ans+=(n-x)*m;24 if(m>x)25 ans+=(m-x)*n;26 for(long long d=1;d*d<=2*x;d++)//枚举d 27 if(2*x%d==0)28 {29 for(long long a=1;a*a<x/d;a++)30 {31 32 long long A=a*a;33 long long B=2*x/d-A;34 long long C=int(sqrt(B+0.5));35 if(C*C!=B)continue;//得出A、B36 if(gcd(a,C)!=1)continue;37 long long k1=(B-A)*d/2;38 long long k2=sqrt(x*x-k1*k1+0.5);39 if(k1*k1+k2*k2!=x*x)continue;40 if(k1>k2)continue;41 if(k1<=n&&k2<=m)42 ans+=(n-k1)*(m-k2)*2;43 if(k1<=m&&k2<=n)44 ans+=(n-k2)*(m-k1)*2; 45 }46 long long k=2*x/d;47 if(2*x%k==0)48 for(long long a=1;a*a<x/k;a++)49 {50 long long A=a*a;51 long long B=2*x/k-A;52 long long C=sqrt(B+0.5);53 if(gcd(a,C)!=1)continue;54 if(C*C!=B)continue;//得出A、B55 long long k1=(B-A)*k/2;56 long long k2=sqrt(x*x-k1*k1+0.5);57 if(k1*k1+k2*k2!=x*x)continue;58 if(k1>k2)continue;59 if(k1<=n&&k2<=m)60 ans+=(n-k1)*(m-k2)*2;61 if(k1<=m&&k2<=n)62 ans+=(n-k2)*(m-k1)*2;63 }64 }65 printf("%I64d ",ans);66 }67 return 0;68 }我不爱奎奎。
NOIP模拟题——计数