Q1 小平方

问题描述

小蓝发现, 对于一个正整数 $n$ 和一个小于 $n$ 的正整数 $v$, 将 $v$ 平方后对 $n$ 取余可能小于 $n$ 的一半, 也可能大于等于 $n$ 的一半。

请问, 在 1 到 $n-1$ 中, 有多少个数平方后除以 $n$ 的余数小于 $n$ 的一半。

例如, 当 $n=4$ 时, $1,2,3$ 的平方除以 4 的余数都小于 4 的一半。

又如, 当 $n=5$ 时, $1,4$ 的平方除以 5 的余数都是 1, 小于 5 的一半。而 2,3 的平方除以 5 的余数都是 $4$ , 大于等于 5 的一半。

输入格式

输入一行包含一个整数 $n$ 。

输出格式

输出一个整数, 表示满足条件的数的数量。

分析:直接循环去做就可以了如果担心非整除性的问题可以把 / 2移到左边变成 * 2.

/*
* @Author: gorsonpy
* @Date:   2023-01-14 15:04:21
* @Last Modified by:   gorsonpy
* @Last Modified time: 2023-01-14 15:07:23
*/
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;

    int cnt = 0;
    for(int i = 1; i < n; ++i)
        if(i * i % n * 2 < n) ++cnt;
    cout << cnt << endl;
    return 0;
}

Q2 超级质数

问题描述

如果一个质数 $P$ 的每位数字都是质数, 而且每两个相邻的数字组成的两位 数是质数, 而且每三位相邻的数字组成的三位数是质数, 依次类推, 如果每相 邻的 $k$ 位数字组成的 $k$ 位数都是质数, 则 $P$ 称为超级质数。

如果把超级质数 $P$ 看成一个字符串, 则这个超级质数的每个子串都是质 数。

例如, 53 是一个超级质数。

请问, 最大的超级质数是多少?

分析这个题目脑算应该比写程序暴力去找更加容易。
1.首先由质数分布规律从直觉上看这样的数字是没有办法太大的。
2.设超级质数的长度为$l$,若长度为$l$的超级质数不存在那么长度$>l$的超极质数都不存在。因为长度大于$l$的超级质数总需要一个长度为l的子节.
3. 超级质数的每一个位置的数字都要是质数那么只有2357满足条件。且2 和 5不能放在个位因为这样的构造显然不能是质数/2 /5。同时相邻的两个数字不能是相同的因为xx的形式显然会有11的因子。
4. 容易枚举出两位数的最大情况是73.三位数的情况为373.四位数则没有可行的解所以三位数的最大答案即为本题答案.

/*
* @Author: gorsonpy
* @Date:   2023-01-14 15:10:53
* @Last Modified by:   gorsonpy
* @Last Modified time: 2023-01-14 15:16:32
*/
#include<iostream>
using namespace std;

int main()
{
    cout << 373 << endl;
}