The number x is called a square root of a modulo n (root( a, n)) if x* x = a (mod n). Write the program to find the square root of number a by given modulo n.
Input
One number K in the first line is an amount of tests ( K ≤ 100000). Each next line represents separate test, which contains inte
Given a list of integers (A1, A2, ..., An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list. Input The input contains several test cases. For each test case, there are two lines. The first line
【题目描述】
求n个点的有向图的强连通图的个数对998244353取模后得结果(无重边，无自环)
定义强连通图为本身为强连通分量的图
【输入格式】
输入一个n表示点数
【输出格式】
输出题目要求的答案
【样例输入】
2
【样例输出】
1
【提示】
对于30%的数据，n<=1000
对于100%的数据，n<=100000
30分的做法详见：网上一篇很好的博客
这个东西是个卷积形式，很容易想到生成函数。
我们来回顾一下两个式子：
f(n)=g(n)+∑k=0n(n−1k−1)f(k)g(n−k) f(n)=g(n)+\sum^{n}_
【题目描述】
求n个点的有向图中强连通图的个数，输出答案对10007取模后得结果(无重边，无自环)
定义强连通图为本身是一个强连通分量的图
【输入格式】
输入一个n表示节点个数
【输出格式】
输出题目要求的答案
【样例输入】
【样例输出】
【提示】
样例解释：
只有一个图，即有边<1,2>和边<2,1>
对于30%的数据，n<=7
对于100%的数据，n<=1000
几个月之前想过强连通图的计数问题，发现根本不可做，暑假集训突然就变成作业了……
这道题的容斥姿势太高超了，功力不够学不来QWQ。
考虑模仿
【题目描述】给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。 【输入格式】第一行一个整数n，表示序列长度。 第二行n个整数，分别表示a1~an。 第三行n个整数，分别表示b1~bn。 第四行n个整数，分别表示c1~cn。 【输出格式】一个整数，表示答案。 【样例输入】5
1 5 3 4 2
2 5 3 4 1
1 2 5 3 4【样例输出】3【样例解释】满足条件的(i,j)共有以下三对： (1,2) (1,3) (1,4) 【数据范围与约定】对于30%的数据，n<
描述给定一个长度为 n 的非负整数序列 a[1..n]。 你每次可以花费 1 的代价给某个 a[i] 加1或者减1。 求最少需要多少代价能将这个序列变成一个不上升序列。 输入第一行一个正整数 n。 接下来 n 行每行一个非负整数，第 i 行表示 a[i]。 1 ≤ n ≤ 500000 0 < a[i] ≤ 109 输出一个非负整数，表示答案。 样例解释[5,3,4,5] -> [5,4,4,4] 样例输入 4
5
3
4
5样例输出 2&nbs
题目描述输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。例如 1，-3,5,1，-2,3当m=4时，S=5+1-2+3=7当m=2或m=3时，S=5+1=6 输入格式第一行两个数n,m第二行有n个数，要求在n个数找到最大子序和 输出格式一个数，数出他们的最大子序和 提示数据范围：100%满足n,m<=300000 样例数据输入样例 #1输出样例 #16 4
1 -3 5 1 -2 37本题我们要找一个不超过M长度的和最大的子段(可以不取)。那么直接把所有前缀和求出来，For一遍每一个右端点，用单调队列维护一下前面m个以内最小的前缀和是多少就
【题目描述】对于给定的字符串S，我们想知道它有多少个不同的回文子串。 【输入】一行，一个长度不超过100000的仅小写字母构成的字符串。 【输出】一个整数，代表不同的回文子串个数。 【输入样例】abcd 【输出样例】4 【提示】有20%的数据，输入字符串的长度不超过1000。 本题有后缀数组的O(n log n)算法，但是既然咱们有回文自动机不是板子题就轻松切掉了嘛。于是又水了一题…… #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int
给出一个数N，输出小于等于N的所有数，两两之间的最大公约数之和。
相当于计算这段程序（程序中的gcd(i,j)表示i与j的最大公约数）：
由于结果很大，输出Mod 1000000007的结果。
G=0;for(i=1;i<N;i++)for(j=1;j<=N;j++){ G = (G + gcd(i,j)) % 1000000007;}
Input
输入一个数N。(2 <= N <= 10^10)
Output
输出G Mod 1000000007的结果。
Input示例
100
Output示例
31080
推导：
&am
出一个数N，输出小于等于N的所有数，两两之间的最小公倍数之和。
相当于计算这段程序（程序中的lcm(i,j)表示i与j的最小公倍数）：
由于结果很大，输出Mod 1000000007的结果。
G=0;for(i=1;i< N;i++)for(j=1;j<=N;j++){ G = (G + lcm(i,j)) % 1000000007;}
Input
输入一个数N。(2 <= N <= 10^10)
Output
输出G Mod 1000000007的结果。
Input示例
4
Output示例
72
推导：
G(
Rockdu's Blog