【C++板块提升计划】梦想护卫舰 第18关 解密（2）【原创】【答题有奖】
本帖最后由 zhangjinxuan 于 2023-2-3 11:29 编辑上一关：旋转与回文
梦想护卫舰 第18关 解密
为了救出 zhangjinxuan，你们只好先放下宝箱，向远处的山奔去
奇怪的是，这座山居然用一道高高的围墙围着，似乎里面有什么神秘的东西
突然，你们在山上发现了……UFO??!（歪星仁？！）
管不了这么多了，进去救人要紧
这是，你们面前的围墙突然变成了 T 道密码门，我们又要来解密了……（歪星仁领地已成功确认）
每一道密码门会给定正整数字 n， 请问 a^2 + n = b^2 一共有多少非负整数解（含0）？
解法数量就是密码
输入格式
T
N1 N2 ... NT
输出格式
一行 T 个数字，表示每个不定方程的解法总数
输入样例1
5
2020 2021 2022 2023 2024
输出样例1
2 2 0 3 4
输入样例2
10
10007 114514 993264353 65536 65535 376542 376544 9000000 3000000 1000000
输出样例2
1 0 8 8 8 0 12 53 35 18
注意，本样例属于 Extra Test 其中之一，这个超时了没关系~
数据范围
对于 100% 的数据，保证 1 <= n, T <= 1000
你别以为这是水题，这个可是有 Extra Test 的哦！
Extra Test 介绍：
当你 100 分的时候，就会开始测试Extra Test
一般情况下，Extra Test 如果没有通过，会扣三分
通过了也不会给你加分
Extra Test 的数据范围与 正常Test 100%数据是一样的
不过这道题不一样，没通过扣5分，数据也不一样：（就是玩~）
Extra Test有三个，这三个Extra Test保证 1 <= (sigma sqrt(n)) * t <= 1e7, 1 <= n <= 1e9
C/C++时间限制：1000ms
C/C++空间限制：256mb
其他语言时间限制：3000ms
其他语言空间限制：1024mb
注意：本题个人原创，转载请注明出处
static/image/hrline/1.gif
答案与解析
**** Hidden Message *****
最佳战士排行榜
|第一名|第二名|第三名
名字|tommyyu|sfpxx|元豪
链接|戳我|戳我|戳我
语言|Python|Scratch|Python
效率|546ms|无|205ms
代码得分|100|60|60
综合得分|100|70|70
奖励|5鱼币5荣誉+“最佳答案(另一贴)”|3鱼币3荣誉+"最佳答案"(本贴)|2鱼币2荣誉
/*综合评分会参照运行时间（代码效率），代码长度，代码可读性，解题思路，代码得分等来进行评分*/
答题规则
1. 不能抄题解，否则无奖励，可能还会扣分;
2. 爆零的代码，视为普通回帖，不会奖励；
3. 语言任意。
4. 当您遇到问题时，您可以回贴提问，我会为您解答
奖励规则
1. 奖励3天后统一发，3天内发布的题解才有效；
2. 提供完整题解，但没有上排行榜，奖励1鱼币+1荣誉；
3. 高于1鱼币1荣誉的奖励，仅给排行榜上的鱼油（因为经济原因，请谅解）；
4. 因为额度原因，部分鱼油可能下一天才能奖励。
**** Hidden Message *****
static/image/hrline/1.gif
下一关：铺地毯
创作不易，如果你喜欢，别忘了评分、顶{:10_281:}
本关满意度调查 zhangjinxuan 发表于 2023-1-30 18:20
https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=223880&pid=6130703
改完了def prime():
global primes
def is_prime(n):
if n<2: return False
return all(n%i for i in range(2, int(n**0.5+1)))
primes =
def count(yinshu, exp_2):
# print(yinshu, exp_2)
if exp_2 == 0: return yinshu // 2 + yinshu % 2
if exp_2 == 1: return 0
s = (yinshu // 2) * (exp_2-1)
s += (yinshu % 2) * (exp_2 // 2)
return s
def count_yinshu(n):
#print(n, end = ' ')
i = 1
yinshu = dict()
try:
while n != 1:
if n < primes and n != 1: return 2
while n % primes == 0:
# print(n)
yinshu] = yinshu.get(primes, 0) + 1
n = n // primes
i += 1
except:
yinshu = 1
s = 1
for i in yinshu:
s *= (yinshu+1)
return s
def count_2_exp(n):
exp_2 = 0
while not n % 2:
n //= 2
exp_2 += 1
return exp_2, n
def count_n(n):
exp_2, new_n = count_2_exp(n)
return count(count_yinshu(new_n), exp_2)
input()
n = list(map(int, input().split()))
#import time
#start = time.time()
prime()
for i in n:
print(count_n(i), end = ' ')
#end = time.time()
#print('\n', start - end, sep = '')
本帖最后由 sfqxx 于 2023-1-31 17:18 编辑
zhangjinxuan 发表于 2023-1-30 15:23
嘿嘿嘿，还是数学题难
直接按照题解思路做不就得了吗？
肝了100分钟，修复了30分钟bug
可算做出来了
因为Scratch难做，所以运行正确可以给我最佳答案吗？（因为tommyu已经够多了，反正这次是第一）
嘿嘿，顺便赚一丢丢鱼币（附件购买）{:10_279:}
如果超时间没关系吧（偶数需要30秒，不过奇数可以快点）（这是最新版，之前的会超时）
下载直接改扩展名就好了（sb3){:10_256:} {:10_250:}不知道能不能过
T = int(input())
N = input().split()
p =
for i in range(T):
for a in range(int(N)):
for b in range(int(N)):
if pow(a, 2) + int(N) == pow(b, 2):
p += 1
for i in range(T):
print(p, end=' ')
菜鸟的答案{:10_250:} 语言任意？
是时候用Scratch了{:10_279:} sfqxx 发表于 2023-1-30 14:52
语言任意？
是时候用Scratch了
啊，啊，啊{:10_277:} sfqxx 发表于 2023-1-30 14:52
语言任意？
是时候用Scratch了
你真能钻bug{:10_306:}
但我好奇你怎么做…… sfqxx 发表于 2023-1-30 14:52
语言任意？
是时候用Scratch了
嘿嘿嘿，还是数学题难{:10_256:} zhangjinxuan 发表于 2023-1-30 15:23
嘿嘿嘿，还是数学题难
然我看看题解
磨刀不误砍柴工{:10_256:} sfqxx 发表于 2023-1-30 15:37
然我看看题解
磨刀不误砍柴工
{:10_256:} {:10_279:} 输入样例2为什么连Extra Test的数据范围都超了？ 有没有时间限制啊{:10_245:}{:10_245:}
我写的代码运行差点以为假死了{:10_250:}{:10_250:} 元豪 发表于 2023-1-30 16:42
有没有时间限制啊
我写的代码运行差点以为假死了
1s 本帖最后由 zhangjinxuan 于 2023-1-30 16:57 编辑
tommyyu 发表于 2023-1-30 16:38
输入样例2为什么连Extra Test的数据范围都超了？
我改一改：
1 <= (sigma sqrt(n)) * t <= 1e7 本帖最后由 tommyyu 于 2023-1-30 17:06 编辑
primes =
# 上面懒得写成线性筛了，如果有要求不能打表就改成线性筛，1~1000以内的素数
def count(yinshu, exp_2):
if exp_2 == 0: return yinshu // 2 + yinshu % 2
if exp_2 == 1: return 0
s = (yinshu // 2) * (exp_2-1)
s += (yinshu % 2) * (exp_2 // 2)
return s
def count_yinshu(n):
try:
#print(n, end = ' ')
i = 1
yinshu = dict()
while n != 1:
#print(n)
while n % primes == 0:
yinshu] = yinshu.get(primes, 0) + 1
n = n // primes
i += 1
s = 1
for i in yinshu:
s *= (yinshu+1)
#print(s)
return s
except:
return 2
def count_2_exp(n):
exp_2 = 0
while not n % 2:
n //= 2
exp_2 += 1
return exp_2, n
def count_n(n):
exp_2, new_n = count_2_exp(n)
return count(count_yinshu(new_n), exp_2)
input()
n = list(map(int, input().split()))
#import time
#start = time.time()
for i in n:
print(count_n(i), end = ' ')
#end = time.time()
#print('\n', end - start, sep = '') tommyyu 发表于 2023-1-30 16:58
建议写线性筛，因为，1 <= n <= 1e9{:10_282:}
这样一来，就得需要4万以内的质数 tommyyu 发表于 2023-1-30 16:58
1 <= (sigma sqrt(n)) * t <= 1e7, 1 <= n <= 1e9
再加一个条件吧，免得有些人被 long long 坑了{:10_306:}
（因为这样 n 可能等于 1e14，t = 1……） zhangjinxuan 发表于 2023-1-30 17:07
再加一个条件吧，免得有些人被 long long 坑了
（因为这样 n 可能等于 1e14，t = 1……）
改好了{:10_256:}def prime():
global primes
def is_prime(n):
if n<2: return False
return all(n%i for i in range(2, int(n**0.5+1)))
primes =
def count(yinshu, exp_2):
if exp_2 == 0: return yinshu // 2 + yinshu % 2
if exp_2 == 1: return 0
s = (yinshu // 2) * (exp_2-1)
s += (yinshu % 2) * (exp_2 // 2)
return s
def count_yinshu(n):
try:
#print(n, end = ' ')
i = 1
yinshu = dict()
while n != 1:
if n < primes and n != 1: return 2
while n % primes == 0:
#print(n)
yinshu] = yinshu.get(primes, 0) + 1
n = n // primes
i += 1
s = 1
for i in yinshu:
s *= (yinshu+1)
#print(s)
return s
except:
return 2
def count_2_exp(n):
exp_2 = 0
while not n % 2:
n //= 2
exp_2 += 1
return exp_2, n
def count_n(n):
exp_2, new_n = count_2_exp(n)
return count(count_yinshu(new_n), exp_2)
input()
n = list(map(int, input().split()))
#import time
#start = time.time()
#prime()
for i in n:
print(count_n(i), end = ' ')
#end = time.time()
#print('\n', start - end, sep = '')
tommyyu 发表于 2023-1-30 17:24
改好了
我都开 long long 了，结果还是不一样{:10_291:}
#include <bits/stdc++.h>
using namespace std;
int t;
long long n;
long long solve(long long n) {
if (n % 2 == 0) {
long long res = 0;
for (long long i = 2; 1LL * i * i <= n; i += 2) {
if (n % i == 0 && n / i % 2 == 0) ++res;
}
return res;
} else {
long long res = 0;
for (long long i = 1; 1LL * i * i <= n; i += 2) {
if (n % i == 0) ++res;
}
return res;
}
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%lld", &n);
printf("%lld ", solve(n));
}
} zhangjinxuan 发表于 2023-1-30 17:39
我都开 long long 了，结果还是不一样
{:10_282:} 本帖最后由 zhangjinxuan 于 2023-1-30 17:43 编辑
tommyyu 发表于 2023-1-30 17:24
改好了
这组数据：
1
993264353
我都怀疑 993264353 不是质数了{:10_284:}
本来就不是 zhangjinxuan 发表于 2023-1-30 17:42
这组数据：
我都怀疑 993264353 不是质数了
好像本来就不是