DescriptionGiven n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz. InputThere are several test cases. For each test case, standard input
Description
Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each te
背景用糖果来引诱小朋友学习是最常用的手法，绵羊爸爸就是用糖果来引诱萌萌学习博弈的。 描述他把糖果分成了两堆，一堆有A粒，另一堆有B粒。他让萌萌和他一起按照下面的规则取糖果：每次可以任意拿走其中一堆糖果；如果这时候另一堆糖果数目多于1粒，就把它任意分成两堆，否则就把剩下的一粒糖果取走并获得这次博弈的胜利。胜利者将获得所有的糖果。萌萌想要得到所有的糖果，而绵羊爸爸想把糖果留下以便下一次利用。现在由萌萌先取糖果，旁观的小朋友们想知道萌萌是否有必胜策略。 格式输入格式本题有多组测试数据（不超过100组）。每组数据包括两行，第一行为A，第二行为B。1 ≤ A,B ≤ 2^127。输入数据以一个 -1 结
给出一个数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(
莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下： 如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。 如果一个数不包含平方因子，并且有k个不同的质因子，那么miu(n) = (-1)^k。例如：miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。 给出一个区间[a,b]，S(a,b) = miu(a) + miu(a + 1) + ...... miu(b)。 例如：S(3
Description
Panda has received an assignment of painting a line of blocks. Since Panda is such an intelligent boy, he starts to think of a math problem of painting. Suppose there are N blocks in a line and each block can be paint red, blue, green or yellow. For some myterious reasons, Panda want bo
Problem Description We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China! “Oh, God! How terrible! ”Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out.
Description我们讲一个悲伤的故事。 从前有一个贫穷的樵夫在河边砍柴。 这时候河里出现了一个水神，夺过了他的斧头，说： “这把斧头，是不是你的？” 樵夫一看：“是啊是啊！” 水神把斧头扔在一边，又拿起一个东西问： “这把斧头，是不是你的？” 樵夫看不清楚，但又怕真的是自己的斧头，只好又答：“是啊是啊！” 水神又把手上的东西扔在一边，拿起第三个东西问： “这把斧头，是不是你的？” 樵夫还是看不清楚，但是他觉得再这样下去他就没法砍柴了。 于是他又一次答：“是啊是啊！真的是！” 水神看着他，哈哈大笑道： “你看看你现在的样子，真是丑陋！” 之后就消失了。 樵夫觉得很坑爹，他今天
题目描述给出两个n位10进制整数x和y，你需要计算x*y。 输入输出格式输入格式： 第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。 输出格式： 输出一行，即x*y的结果。（注意判断前导0） 输入输出样例输入样例#1： 复制1
3
4 输出样例#1： 复制12 说明数据范围： n<=60000 来源：bzoj2179 本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。 寻找了很久，最终还是发现算法导论的FFT讲解的是最详细的，前置技能：复数四则运算，矩阵
Rockdu's Blog