洛谷P2508 [HAOI2008]圆上的整点

题目描述

求一个给定的圆\((x^2+y^2=r^2)\)，在圆周上有多少个点的坐标是整数。

输入输出格式

输入格式：

\(r\)

输出格式：

整点个数

解题思路

哔哩哔哩
看完这个视频后，问题转化成分解质因数，只不过将视频中的\(\sqrt{R}\)变成了\(R\)而已。则高斯素数的无论多少次方都毫无影响，\(4n+3\)型素数的影响由于幂次的翻倍而变成\(2*cnt+1\)。

AC代码

#include<stdio.h>
#include<math.h>
int main(){
    int i,n,cnt=0,ans=1;
    scanf("%d",&n);
    for(i=2;i*i<=n;i++,cnt=0){
        if(n%i==0){
            while(n%i==0)n/=i,cnt++;
            if(i%4==1)ans*=2*cnt+1;
        }
    }
    if(n>1&&n%4==1)ans*=2*1+1;
    printf("%d",4*ans); 
    return 0;
}

洛谷P2529 [SHOI2001]击鼓传花

题目描述

HC(Happy Child )小朋友最近经常在教室里跟同学一起玩击鼓传花的游戏，规则是第\(n\)个拿到花的小朋友必须说出\(n!\)最后一位非\(0\)的数字，如此循环游戏，如果谁讲错了就得罚唱一支歌曲。
经过几次游戏，HC小朋友认为只要把前一个小朋友说得数字去乘以\(n\)，说出得到的数的最后一位非\(0\)的数字就可以了，可惜HC小朋友这次轮到了第\(15\)个，结果被罚了唱歌(应该是\(8\)，但是HC小朋友却说了\(3\))。
HC小朋友不希望这样的事情再次发生，所以希望你能编写一个程序，能够计算出\(n!\)的最后一位非\(0\)的数字。

输入输出格式

输入格式：

输入有\(5\)行，第\(i(1≤i≤5)\)行是一个\(n(1≤n≤10^{100}\))。

输出格式：

输出有\(5\)行。
第I行对应输入中第I行的n的阶乘的最后一位非\(0\)的数字。

解题思路

下面所有等号的意义是最后一位非零数相等。

观察得（关键步骤）：

\((1) (1*2*3*4*6*7*8*9)%10=6\)，而\(6^k %10=6(k\)∈\(N)\)。

\((2) p*5=p*8\)

第二步的证明：
\(p*5=p*10/2=p/2\)。
乘到\(5\)，则必然已经是\(4\)的倍数。
\(2/2=6,4/2=2,6/2=8,8/2=4\)
\(2*8=6,4*8=2,6*8=8,8*8=4\)
证毕。

\(0.\)于是，将所有\(5\)的倍数剔除掉（留待后面计算）后，先算出个位数（除去\(5\)）的乘积\(%10\)的结果
此时忽略掉的问题是：
\(1.\)十位数及以上的影响
\(2. 5\)的倍数的影响
其中，\(5\)的倍数影响有两方面：
\(2.(1)5\)本身
\(2.(2)\)除去\(5\)的其他因子影响
而\(2.2\)可以通过回到\(0\)递归实现。
注意到，\(6*8=8,1*8=8\)；\(8^{[0,1,2,3]}=1,8,4,2\)。所以，\(2.1\)和\(1\)可以通过一个\(pre\)数组实现。可以预处理出\(pre\)数组为\([6,8,4,2]\)。

举个例子

\(n=917\)
\(n!=(1*2*3*4*6*7*8*9*11*12*13*14*16*17*18*19*...*916)*(5*10*...*915)\)

\(=(6*6*...*6*911*912*913*914*916)*(5^{\left\lfloor 917\over 5\right\rfloor})*(1*2*3*4*6*7*8*9*...*\left\lfloor 917\over 5\right\rfloor)\)

\(=(1*2*3*4*6)*6*(8^{\left\lfloor 917\over 5\right\rfloor})(1*2*3*4*6*7*8*9*...*\left\lfloor 917\over 5\right\rfloor)\)

其中，\(6*(8^{\left\lfloor 917\over 5\right\rfloor})\)可由\(pre\)数组推得；\((1*2*3*4*6*7*8*9*...*\left\lfloor 917\over 5\right\rfloor)\)则可由递归算出。
问题得解。

AC代码

fre=[6,8,4,2]
for j in range(1,6):
    cnt=0
    ans=1
    n=int(input())
    if(n==1):
        print(1)
    else:
        while(n>0):
            for i in range(1,n%10+1):
                if(i!=5):
                    ans*=i
            n//=5
            ans*=fre[n%4]
            ans%=10
        print(ans)

CF1091D New Year and the Permutation Concatenation

题目描述

Let \(n\) be an integer. Consider all permutations on integers \(1\) to \(n\) in lexicographic order, and concatenate them into one big sequence \(p\). For example, if \(n=3\), then \(p=[1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1]\). The length of this sequence will be \(n⋅n!\).
Let \(1≤i≤j≤n⋅n!\)be a pair of indices. We call the sequence \((p_i,p_{i+1},…,p_{j−1},p_j)\)
a subarray of \(p\). Its length is defined as the number of its elements, i.e., \(j−i+1\). Its sum is the sum of all its elements, i.e., \(\sum_{k=i}^j p_k\).
You are given \(n\). Find the number of subarrays of \(p\)of length \(n\)having sum \(n(n+1)/2\). Since this number may be large, output it modulo \(998244353\)(a prime number).

输入输出格式

输入格式：

The only line contains one integer \(n(1≤n≤10^6)\), as described in the problem statement.

输出格式：

Output a single integer — the number of subarrays of length \(n\) having sum \(n(n+1)/2\), modulo \(998244353\).

解题思路

\(p\)的选取：不重不漏、连续的\(1-n\)的排列。
首先，第一个数字不同的排列间必然不能产生序列\(p\)。原因：下一个排列的所有数字必然不全位于上一个排列的后面。
所以可以只考虑第一个数字为\(k\)的情况，最后乘以\(k\)即可。

设\(ans[i]\)为\(n=i\)时符合条件的排列种数。

设\(n=k\)已选出合适排列（称为上一级排列），则考虑\(n=k+1\)时，放进新来的\(k+1\)后，有多少种符合题意的子列。
放进新来的\(k+1\)后，其实是向原序列中头部分配了\(k+1\)，也即向\(ans[k]\)几乎均匀插入\(k+1\)。

故，只有两种可以构成题目中子列的方式：
\((1)\)所有上一级排列之中加上\(k+1\)的新排列（\(ans[k]\)种）
\((2)\)所有头部为\(k+1\)的新形成的排列（\(k!\)种）
其中，这两种方式重复的种数为所有元素降序排列的种数（\(1\)种）。

故得到递推关系式：\(ans[i]=(ans[i-1]+(n-1)!-1)*i\)。

AC代码

#include<stdio.h>
long long jc[1000010]={1,1},ans[100010]={0,1},w=998244353;
int main(){
    int i,n;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        jc[i]=jc[i-1]*i%w;
        ans[i]=(ans[i-1]-1+jc[i-1])*i%w;
    }
    printf("%I64d",ans[n]);
    return 0;
}