传送门
题意：计算σ0(i3)" role="presentation" style="position: relative;">σ0(i3)σ0(i3)\sigma_0(i^3)的前缀和
以前雅礼集训的时候就听说过这题，好像是洲阁筛板子？
但是如今世道不同了，Min_25" role="presentation" style="position: relative;">Min_25Min_25Min\_25筛可以把这种东西吊起来筛！
当p∈Prime,f(pc)=3c+1" role="present
传送门
题意：计算σ0(ik)\sigma_0(i^k)的前缀和
一道牛逼题目，Min_25Min\_25筛写的很简短。
当p∈Prime,f(pc)=ck+1p\in Prime,f(p^c)=ck+1
且当p∈Prime,f(p)=k+1p\in Prime,f(p)=k+1
又因为前缀和∑ni=1k+1=n(k+1)\sum^n_{i=1}k+1=n(k+1)可以O(1)O(1)
直接Min_25Min\_25筛就行了，复杂度O(1011)O(10^{11})能过。
#include<cstdio>#include<algorithm>#
题目描述
给你一个质数p" role="presentation" style="position: relative;">ppp以及n" role="presentation" style="position: relative;">nnn组询问， 判定给定的r" role="presentation" style="position: relative;">rrr是否为p" role="presentation" style="position: relative;">ppp的原根。
输入输出格式
输入格式
题目有多组测试数据。
每组测试数据的第一行两
后缀数组模板题，直接看注释就好了 #include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
char s[maxn]; LL ans;
int SA[maxn], SA2[maxn], RK[maxn], tot[maxn], H[maxn];
//SA : 第一关键字排名为i的开头下标
//SA2 : 第二关键字排名为i的开头下标
//RK : 原字符串中下标为i后缀的
Given a string, we need to find the total number of its distinct substrings. InputT- number of test cases. T<=20; Each test case consists of one string, whose length is <= 1000 OutputFor each test case output one number saying the number of distinct substrings. ExampleSample Input: 2 CCCCC ABA
A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the set of lowercase letters. Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string. Now your task is a bit harder, for some given strings, find the l
LCS - Longest Common Substringno tags A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the set of lowercase letters. Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string. Now your task is si
Rockdu's Blog