lightoj1008

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1008 - Fibsieve`s Fantabulous Birthday

Among these gifts there was an N x N glass chessboard that had a light in each of its cells. When the board was turned on a distinct cell would light up every second, and then go dark.Fibsieve had a fantabulous (yes, it's an actual word) birthday party this year. He had so many gifts that he was actually thinking of not having a party next year.

The cells would light up in the sequence shown in the diagram. Each cell is marked with the second in which it would light up.

In the first second the light at cell (1, 1) would be on. And in the 5th second the cell (3, 1) would be on. Now, Fibsieve is trying to predict which cell will light up at a certain time (given in seconds). Assume that N is large enough.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case will contain an integer S (1 ≤ S ≤ 10¹⁵) which stands for the time.

Output

For each case you have to print the case number and two numbers (x, y), the column and the row number.

Sample Input	Output for Sample Input
382025	Case 1: 2 3Case 2: 5 4Case 3: 1 5

题目类型：简单递推

算法分析：首先得到对角线上数的递推公式，然后求得最接近输入数S的对角线上的数ans，然后判断S是否在[ans – (temp - 1), ans + (temp + 1)]中，其中temp表示对角线元素的坐标(temp,temp)，然后再分类讨论即可

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 366 + 66;

long long F (long long val)
{
    return val * val - val + 1;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        printf ("Case %d: ", flag++);

        long long val, ans;
        scanf ("%lld", &val);

        long long temp = (long long) sqrt ((double) val);

        while (1)
        {
            ans = F (temp);
            if (val >= ans - (temp - 1) && val <= ans + (temp - 1))
                break;

            if (val < ans - (temp - 1))
                temp--;

            else
                temp++;
        }

        if (temp % 2)
        {
            if (val >= ans - (temp - 1) && val <= ans)
                printf ("%lld %lld\n", temp, temp - (ans - val));

            else
                printf ("%lld %lld\n", temp - (val - ans), temp);
        }

        else
        {
            if (val >= ans - (temp - 1) && val <= ans)
                printf ("%lld %lld\n", temp - (ans - val), temp);

            else
                printf ("%lld %lld\n", temp, temp - (val - ans));
        }
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 366 + 66;

long long F (long long val)

{

return val * val - val + 1;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

cin >> t;

while (t--)

{

printf ("Case %d: ", flag++);

long long val, ans;

scanf ("%lld", &val);

long long temp = (long long) sqrt ((double) val);

while (1)

{

ans = F (temp);

if (val >= ans - (temp - 1) && val <= ans + (temp - 1))

break;

if (val < ans - (temp - 1))

temp--;

else

temp++;

}

if (temp % 2)

{

if (val >= ans - (temp - 1) && val <= ans)

printf ("%lld %lld\n", temp, temp - (ans - val));

else

printf ("%lld %lld\n", temp - (val - ans), temp);

}

else

{

if (val >= ans - (temp - 1) && val <= ans)

printf ("%lld %lld\n", temp - (ans - val), temp);

else

printf ("%lld %lld\n", temp, temp - (val - ans));

}

return 0;

}

lightoj1007

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

1007 - Mathematically Hard

In this problem, you will be given two integers a and b. You have to find the summation of the scores of the numbers from a to b (inclusive). The score of a number is defined as the following function.Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.

score (x) = n², where n is the number of relatively prime numbers with x, which are smaller than x

For example,

For 6, the relatively prime numbers with 6 are 1 and 5. So, score (6) = 2² = 4.

For 8, the relatively prime numbers with 8 are 1, 3, 5 and 7. So, score (8) = 4² = 16.

Now you have to solve this task.

Input

Input starts with an integer T (≤ 10⁵), denoting the number of test cases.

Each case will contain two integers a and b (2 ≤ a ≤ b ≤ 5 * 10⁶).

Output

For each case, print the case number and the summation of all the scores from a to b.

Sample Input	Output for Sample Input
36 68 82 20	Case 1: 4Case 2: 16Case 3: 1237

题目类型：欧拉函数

算法分析：使用递推的方法将5e6以内的欧拉函数值算出来，进而求前缀和，最后直接查询即可，注意本题数据比较大，只能使用unsigned long long定义euler数组

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 5000000 + 66;

unsigned long long euler[maxn];

void GetEuler ()
{
    for (int i = 0; i < maxn; i++)
        euler[i] = i;

    for (int i = 2; i < maxn; i += 2)
        euler[i] >>= 1;

    for (int i = 3; i < maxn; i += 2)
    {
        if (euler[i] == i)
        {
            for (int j = i; j < maxn; j += i)
                euler[j] = euler[j] - euler[j] / i;
        }
    }
}

void init ()
{
   euler[1] = euler[1] * euler[1];

    for (int i = 2; i < maxn; i++)
        euler[i] = euler[i-1] + euler[i] * euler[i];

}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    GetEuler ();

    init ();

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        int a, b;
        scanf ("%d%d", &a, &b);

        printf ("%llu\n", euler[b] - euler[a-1]);
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 5000000 + 66;

unsigned long long euler[maxn];

void GetEuler ()

{

for (int i = 0; i < maxn; i++)

euler[i] = i;

for (int i = 2; i < maxn; i += 2)

euler[i] >>= 1;

for (int i = 3; i < maxn; i += 2)

{

if (euler[i] == i)

{

for (int j = i; j < maxn; j += i)

euler[j] = euler[j] - euler[j] / i;

}

void init ()

{

euler[1] = euler[1] * euler[1];

for (int i = 2; i < maxn; i++)

euler[i] = euler[i-1] + euler[i] * euler[i];

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

GetEuler ();

init ();

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int a, b;

scanf ("%d%d", &a, &b);

printf ("%llu\n", euler[b] - euler[a-1]);

}

return 0;

}

lightoj1002

maksyuki 发表于 oj 分类，标签: 图论-最短路

27 8月 2015

1002 - Country Roads

For example, in the above picture, if we want to go from 0 to 4, then we can chooseI am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

1) 0 - 1 - 4 which costs 8, as 8 (1 - 4) is the maximum road we used

2) 0 - 2 - 4 which costs 9, as 9 (0 - 2) is the maximum road we used

3) 0 - 3 - 4 which costs 7, as 7 (3 - 4) is the maximum road we used

So, our result is 7, as we can use 0 - 3 - 4.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000)indicating that there is a road between u and v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.

Output

For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print 'Impossible'.

Sample Input

Output for Sample Input

25 60 1 5

0 1 4

2 1 3

3 0 7

3 4 6

3 1 8

5 4

0 1 5

0 1 4

2 1 3

3 4 7

Case 1:403

Case 2:

Impossible

Note

Dataset is huge, user faster I/O methods.

题目类型：最大容量路(bellman-ford)

算法分析：使用边表存储边的信息，然后使用bellman-ford迭代n – 1次计算dis数组的值，dis[i]表示节点i到目标节点的最大容量值，递推公式为

dis[edge[j].u] = min (dis[edge[j].u], max (edge[j].w, dis[edge[j].v]));注意使用Floyd会TLE

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 16000;

struct Node
{
    int u, v, w;
};

Node edge[maxn];

int dis[666];
int n, m;

void bellman_ford (int val)
{
    int i;
    for (i = 0; i < n; i++)
        dis[i] = INF;

    dis[val] = 0;
    for (i = 1; i < n; i++)
    {
        int j;
        for (j = 0; j < m; j++)
        {
            dis[edge[j].u] = min (dis[edge[j].u], max (edge[j].w, dis[edge[j].v]));
            dis[edge[j].v] = min (dis[edge[j].v], max (edge[j].w, dis[edge[j].u]));
        }
    }
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        cout << "Case " << flag++ << ":" << endl;

        scanf ("%d%d", &n, &m);

        int i;
        for (i = 0; i < m; i++)
        {
            scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
        }

        int tar;
        scanf ("%d", &tar);

        bellman_ford (tar);

        for (i = 0; i < n; i++)
        {
            if (i == tar)
                printf ("0\n");

            else if (dis[i] < INF)
                printf ("%d\n", dis[i]);

            else
                printf ("Impossible\n");
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 16000;

struct Node

{

int u, v, w;

};

Node edge[maxn];

int dis[666];

int n, m;

void bellman_ford (int val)

{

int i;

for (i = 0; i < n; i++)

dis[i] = INF;

dis[val] = 0;

for (i = 1; i < n; i++)

{

int j;

for (j = 0; j < m; j++)

{

dis[edge[j].u] = min (dis[edge[j].u], max (edge[j].w, dis[edge[j].v]));

dis[edge[j].v] = min (dis[edge[j].v], max (edge[j].w, dis[edge[j].u]));

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

cout << "Case " << flag++ << ":" << endl;

scanf ("%d%d", &n, &m);

int i;

for (i = 0; i < m; i++)

{

scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);

}

int tar;

scanf ("%d", &tar);

bellman_ford (tar);

for (i = 0; i < n; i++)

{

if (i == tar)

printf ("0\n");

else if (dis[i] < INF)

printf ("%d\n", dis[i]);

else

printf ("Impossible\n");

}

return 0;

}

bzoj3229

maksyuki 发表于 oj 分类，标签: DP-区间DP

27 8月 2015

3229: [Sdoi2008]石子合并

Description

在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将N堆石子合并成一堆的最小得分。

阅读全文 »

bzoj2818

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

2818: Gcd

Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

Input

一个整数N

阅读全文 »

bzoj2705

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

2705: [SDOI2012]Longge的问题

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

阅读全文 »

bzoj2190

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

2190: [SDOI2008]仪仗队

Description

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

阅读全文 »

sgu112

maksyuki 发表于 oj 分类，标签: 基础算法-高精度

27 8月 2015

a^b-b^a

You are given natural numbers a and b. Find a^b-b^a.

Input

Input contains numbers a and b (1≤a,b≤100).

阅读全文 »

sgu105

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

Div 3

There is sequence 1, 12, 123, 1234, ..., 12345678910, ... . Given first N elements of that sequence. You must determine amount of numbers in it that are divisible by 3.

Input

Input contains N (1<=N<=2³¹ - 1).

Output

Write answer to the output.

Sample Input

Sample Output

题目类型：简单数学

算法分析：打表发现各位和能整除3的数是有规律的，直接按照规律求解即可(任意数模3的取值只有0、1和2)

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100000 + 66;

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    long long n;
	cin >> n;

	if (n == 1)
		cout << "0" << endl;

	else if (n == 2)
		cout << "1" << endl;

	else
	{
        if (n % 3 == 0)
			cout << 2 * (n / 3) << endl;

		else
		{
			int tt = n / 3;
			if (n == 3 * tt + 1)
				cout << 2 * (n / 3) << endl;

			else if(n == 3 * tt + 2)
				cout << 2 * (n / 3) + 1 << endl;
		}

	}
return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100000 + 66;

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

long long n;

cin >> n;

if (n == 1)

cout << "0" << endl;

else if (n == 2)

cout << "1" << endl;

else

{

if (n % 3 == 0)

cout << 2 * (n / 3) << endl;

else

{

int tt = n / 3;

if (n == 3 * tt + 1)

cout << 2 * (n / 3) << endl;

else if(n == 3 * tt + 2)

cout << 2 * (n / 3) + 1 << endl;

}

return 0;

}

sgu104

maksyuki 发表于 oj 分类，标签: DP-线性DP

27 8月 2015

Little shop of flowers

PROBLEM

You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.

Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.

		V A S E S
		1	2	3	4	5
Bunches	1 (azaleas)	7	23	-5	-24	16
	2 (begonias)	5	21	-4	10	23
	3 (carnations)	-21	5	-4	-20	20

According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.

To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.

ASSUMPTIONS

1 ≤ F ≤ 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
F ≤ V ≤ 100 where V is the number of vases.
-50 £ A_ij £ 50 where A_ijis the aesthetic value obtained by putting the flower bunch i into the vase j.

Input

The first line contains two numbers: F, V.
The following F lines: Each of these lines contains V integers, so that A_ij is given as the j’th number on the (i+1)’st line of the input file.

Output

The first line will contain the sum of aesthetic values for your arrangement.
The second line must present the arrangement as a list of F numbers, so that the k’th number on this line identifies the vase in which the bunch k is put.

Sample Input

3 5

7 23 -5 -24 16

5 21 -4 10 23

-21 5 -4 -20 20

Sample Output

2 4 5

题目类型：线性DP+记录路径

算法分析：dp[i][j]表示前i种花在第j个花瓶中所取得的最大特征值。par[i][j]表示前i种花在第j个花瓶取得最大值时从前i-1种花转移来的花瓶序号。状态转移方程为：dp[i][j] += max{dp[i-1][k]} i - 1 <= k < j，最后输出最大值并回溯求解列号

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100 + 66;

int dp[maxn][maxn], par[maxn][maxn], out[maxn], len;

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    int r, w;
    while (cin >> r >> w)
	{
        for (int i = 1; i <= r; i++)
			for (int j = 1; j <= w; j++)
				cin>> dp[i][j];

        for (int i = 1; i <= w; i++)
			par[1][i] = i;

        for (int i = 2; i <= r; i++)
		{
			for (int j = i; j <= w; j++)
			{
				int maxval = -INF;
                for (int k = i - 1; k < j; k++)
				{
                    if (maxval < dp[i-1][k])
					{
						maxval = dp[i-1][k];
						par[i][j] = k;
					}
				}

                dp[i][j] += maxval;
			}
		}

		int maxval = -INF, pos = -1;
		for (int i = r; i <= w; i++)
            if (maxval < dp[r][i])
			{
                maxval = dp[r][i];
                pos = i;
			}

		cout << maxval << endl;

		len = 0;
		for (int i = r; i >= 1; i--)
		{
            out[len++] = pos;
            pos = par[i][pos];
		}

		for (int i = len - 1; i >= 0; i--)
		{
			if (i == len - 1)
				cout << out[i];

			else
				cout << " " << out[i];
		}
	}

return 0;
}

100

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 66;

int dp[maxn][maxn], par[maxn][maxn], out[maxn], len;

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int r, w;

while (cin >> r >> w)

{

for (int i = 1; i <= r; i++)

for (int j = 1; j <= w; j++)

cin>> dp[i][j];

for (int i = 1; i <= w; i++)

par[1][i] = i;

for (int i = 2; i <= r; i++)

{

for (int j = i; j <= w; j++)

{

int maxval = -INF;

for (int k = i - 1; k < j; k++)

{

if (maxval < dp[i-1][k])

{

maxval = dp[i-1][k];

par[i][j] = k;

}

dp[i][j] += maxval;

}

int maxval = -INF, pos = -1;

for (int i = r; i <= w; i++)

if (maxval < dp[r][i])

{

maxval = dp[r][i];

pos = i;

}

cout << maxval << endl;

len = 0;

for (int i = r; i >= 1; i--)

{

out[len++] = pos;

pos = par[i][pos];

}

for (int i = len - 1; i >= 0; i--)

{

if (i == len - 1)

cout << out[i];

else

cout << " " << out[i];

}

return 0;

}

sgu102

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

Coprimes

For given integer N (1<=N<=10⁴) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

Input

Input file contains integer N.

Output

Write answer in output file.

Sample Input

Sample Output

题目类型：Euler函数计算

算法分析：直接使用试除法求解即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100000 + 66;

long long GetEuler (long long val)
{
    long long ans = val;
    for (long long i = 2; i * i <= val; i++)
    {
        if (val % i == 0)
        {
            ans -= ans / i;

            while (val % i == 0)
            {
                val /= i;
            }
        }
    }

    if (val > 1)
        ans -= ans / val;

return ans;
}


int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    long long n;
    cin >> n;

    cout << GetEuler(n) << endl;

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100000 + 66;

long long GetEuler (long long val)

{

long long ans = val;

for (long long i = 2; i * i <= val; i++)

{

if (val % i == 0)

{

ans -= ans / i;

while (val % i == 0)

{

val /= i;

}

if (val > 1)

ans -= ans / val;

return ans;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

long long n;

cin >> n;

cout << GetEuler(n) << endl;

return 0;

}

超客的水墨烟雨

lightoj1008

Input

Output

Sample Input

Output for Sample Input

lightoj1007

Input

Output

Sample Input

Output for Sample Input

lightoj1002

Input

Output

Sample Input

Output for Sample Input

Note

bzoj3229

3229: [Sdoi2008]石子合并

Description

bzoj2818

2818: Gcd

Description

Input

bzoj2705

2705: [SDOI2012]Longge的问题

Description

Input

bzoj2190

2190: [SDOI2008]仪仗队

Description

sgu112

sgu105

sgu104

sgu102

分类目录

标签云

书签

近期评论

2015年8月
一	二	三	四	五	六	日
« 7月				9月 »
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31