## 原【欧拉函数模板题】【前缀和】FareySequence

Problem Description

The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
You task is to calculate the number of terms in the Farey sequence Fn.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10<sup>6</sup>). There are no blank lines between cases. A line with a single 0 terminates the input.

Output

For each test case, you should output one line, which contains N(n) —- the number of terms in the Farey sequence Fn. <b

Sample Input

2

3

4

5

0

Sample Output

1

3

5

9

## 思路：由a / b,gcd(a,b)=1知，当前f(n)是在f（n – 1）的基础上加上以n为分母，与n互质的数为分子的分数，所以f（n）比f（n – 1）增加了1~n内与n互质的数的个数，现在题意就很明显了，就是要求1-N的欧拉函数之和。

#include <iostream>
using namespace std;
typedef long long ll;
const int MAX=1000005;
int oula[MAX];
void init()
{
oula[1]=1;
for(int i=2;i<MAX;i++)
oula[i]=i;
for(int i=2;i<MAX;i++)
if(oula[i]==i)
for(int j=i;j<MAX;j+=i)
oula[j]=oula[j]/i*(i-1);
}
int main()
{
ll n,ans=0;
init();
while(cin>>n&&n)
{
ans=0;
for(int i=2;i<=n;i++)
ans+=oula[i];
cout<<ans<<endl;
}
return 0;
}


## 原SDAU暑假训练第12天做题（2018810）

PS:做题速度大佬们一个比一个快，，菜鸡感到压力很大

## 【leetcode458】【规律题】【突破性思维】可怜的小猪

【leetcode458】【规律题】【突破性思维】可怜的小猪

# 分析

00     01     02     03      04

10     11     12     13      14

20     21     22     23      24

30     31     32     33      34

40     41     42     43      44

java代码：

class Solution {
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {

if(buckets == 1) return 0;

int w = minutesToTest / minutesToDie + 1;
int re = 1;
while(Math.pow(w,re) < buckets)
re ++;

return re;
}
}

class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
if(minutesToTest < minutesToDie)
return 0;
return ceil(log(buckets) / log(floor(minutesToTest/minutesToDie) + 1));
}

};

# 总结

## SDAU暑假训练第七天休息日&第一周总结（201885）

SDAU暑假训练第七天休息日第一周总结（201885）

## 暑假集训第一周总结

#### 一周过去了,谈一下感受:

这一点虽然老师早就给打了预防针，仍然没有预料到会这么大,6天完成两大章内容，虽然有高中的一点基础撑着，仍然是相当吃不消。到了后期虚到几乎就是在在集训室都能睡着的地步。不过学到的东西挺多的，虽然不如大佬们理解的深刻，但对我来说是不小的进步啦

以前觉着学习和体力是分开的，再加上我喜欢思考东西不喜欢运动，所以身体素质差一点，本以为也不是什么大不了的事，我靠脑力照样能养活自己。集训了6天之后才发现，体力是脑力的物质基础，脑力是体力的上层建筑。做ACM的基本都会熬夜，别人熬一次夜只要第二天多睡一会就行了，但是我要好几天才能完全消除负面影响，这几天一直在熬夜，身体一直处于负面循环中，下学期除了学习也应该每周抽些时间锻炼身体。

经历了六天的脑力风暴之后，迎来了宝贵的休息日，本来想就在宿舍放飞一下自我，后来大约10点还是忍不住去613了，五位比我优秀的大佬待在那里学习，然后就跟大佬们一起在那了一天，为自己先前的想法感到羞愧，本来这几天学的就没别人好，哪来的资本去玩？

数学一本通好多地方都很迷，有些地方干脆一笔带过，真是不愧对一本通的称呼，这个时候自己去网上找资料学习就很重要了，（这六天东西倒是没学着点，找东西的本领倒是提升了不少，哈哈）

# 五.睡觉！

## 简易图书馆借还书系统（核心部分）

【第一题】

rentbook()成员函数用于借阅图书。主函数进行测试。说明：这是一个简单的借阅过程。借阅时，假设要借阅的图书是存在的。提示：

*/

#include<iostream>
#include<string>
using namespace std;
class object
{
protected:
string name;
int no;
public:

object(){}
object(string ch,int a):name(ch),no(a)
{}
};
class Book:public object
{
private:
string author;
public:
friend ostream &operator<<(ostream& out,Book &book)
{
out<<"书名:"<<book.name<<"\t编号："<<book.no<<"\t作者："<<book.author<<endl;
return out;
}
Book():object(){}
Book(string ch,int a,string ch1):object(ch,a)
{ author=ch1;
ch="《"+ch;
ch=ch+"》";
cout<<"恭喜您，借阅成功！\n该书信息为："<<endl
<<"------------------------------------------\n"
<<"书名："<<ch<<endl
<<"编号为："<<a<<endl
<<"作者："<<ch1<<endl
<<"------------------------------------------\n";
}
};
{
int num;
Book rent[5];
static int top;
public:
{

cout<<"读者为："<<ch<<endl;
cout<<"借书证号为："<<a<<endl;
cout<<"想要借书的数量为："<<c<<endl;
cout<<"请输入这"<<c<<"本书的书名、编号、作者："<<endl;
}
void rentbook(Book &b)
{
this->rent[top]=b;
top++;
}
void show()
{
cout<<"读者目前持有的图书：\n"
<<"------------------------------------------\n";
for(int i=0;i<top;i++)
cout<<this->rent[i];
cout<<"------------------------------------------\n";

}
};
int main()
{
int top=0;
string a,c,key("123456"),keyin;
char in_choose,system_choose='Y';
int b,d;
do{
printf("请输入您的姓名和借书证号:\n");
cin>>a>>b;
printf("输入您的密码:(默认密码123456)\n");
while(1)
{
cin>>keyin;
if(key!=keyin) cout<<"密码错误，请重试"<<endl;
else
{
cout<<"密码正确\n"<<endl;
break;
}
}
cout<<"请输入想要借书的数量："<<endl;
cin>>d;
for(int i=0;i<d;i++)
{
cout<<"请输入书名和编号和作者："<<endl;
cin>>a>>b>>c;
Book temp(a,b,c);
}
cout<<"--->下一个读者请按请按Y\n--->任意键退出系统\t"<<endl;
cin>>in_choose;
}while (in_choose==system_choose);
cout<<"系统已经退出！"<<endl;
return 0;
}

337

123456

2

——————————————

——————————————

——————————————

——————————————

——————————————

——————————————

Y

123456

1

——————————————

——————————————

——————————————

——————————————
—>下一个读者请按请按Y
—>任意键退出系统
3