首页 > 代码库 > 四方定理（洛谷 1586）
四方定理（洛谷 1586）
题目描述
四方定理是众所周知的：任意一个正整数n，可以分解为不超过四个整数的平方和。例如：25＝12+22+22+42，当然还有其他的分解方案，25＝42+32和25＝52。给定的正整数n，编程统计它能分解的方案总数。注意：25＝42+32和25＝32+42视为一种方案。
输入输出格式
输入格式：
第一行为正整数t(≤100)，接下来t行，每行一个正整数n(≤32768)。
输出格式：
对于每个正整数n，输出方案总数。
输入输出样例
输入样例#1：
12003
输出样例#1：
View Code
48
/* 先用暴力搜一遍，全超时，后用O(n^logn)因为常数问题又超时， 题解的四重循环，就是利用了无重复情况的特点，常数很小，也很好理解。 */#include<cstdio>#include<iostream>#include<cmath>using namespace std;int n;int main(){ freopen("jh.in","r",stdin); int T,n; scanf("%d",&T); int ans=0; while(T--) { scanf("%d",&n); ans=0; for(int i=0;i*i*4<=n;i++) for(int j=i;i*i+j*j*3<=n;j++) for(int k=j;i*i+j*j+k*k*2<=n;k++) { int l=n-i*i-j*j-k*k; int s=(int)sqrt(l); if(s*s==l&&s>=k) ans++; } printf("%d\n",ans); } return 0;}
四方定理（洛谷 1586）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。