这是一套实验室的学长给我们出的一套非常好的题目，思维+算法，非常有价值，在这里总结一下这里的经验与做法

①Watering System &&codeforce 967B

题目描述：

Arkady wants to water his only flower. Unfortunately, he has a very poor watering system that was designed for nn flowers and so it looks like a pipe with nn holes. Arkady can only use the water that flows from the first hole.

Arkady can block some of the holes, and then pour AA liters of water into the pipe. After that, the water will flow out from the non-blocked holes proportionally to their sizes s1,s2,…,sns1,s2,…,sn. In other words, if the sum of sizes of non-blocked holes is SS, and the ii-th hole is not blocked, si⋅A/S liters of water will flow out of it.

What is the minimum number of holes Arkady should block to make at least BB liters of water flow out of the first hole?

Input

The first line contains three integers nn, AA, BB (1≤n≤1000001≤n≤100000, 1≤B≤A≤1041≤B≤A≤104) — the number of holes, the volume of water Arkady will pour into the system, and the volume he wants to get out of the first hole.

The second line contains nn integers s1,s2,…,sns1,s2,…,sn (1≤si≤1041≤si≤104) — the sizes of the holes.

Output

Print a single integer — the number of holes Arkady should block.

Examples

Input

4 10 3
2 2 2 2

Output

1

Input

4 80 20
3 2 1 4

Output

0

Input

5 10 10
1000 1 1 1 1

Output

4

Note

In the first example Arkady should block at least one hole. After that, 10⋅26≈3.33310⋅26≈3.333 liters of water will flow out of the first hole, and that suits Arkady.

In the second example even without blocking any hole, 80⋅310=2480⋅310=24 liters will flow out of the first hole, that is not less than 2020.

In the third example Arkady has to block all holes except the first to make all water flow out of the first hole.

题目大意：一共有n个洞，每个洞有一个s值，记没有被堵上的洞总的s值为sum，问你至少填几个洞能使a*S0/sum>=b

题解思路：我开始本来想贪心，因为怕超时(根据其他同学的提交来看，没有超时)，所以还加了一个二分优化，二分枚举 堵住洞的个数，如果这个数量下，a*S0/sum>=b，我们就继续 缩小范围，毕竟要求最小值嘛，不行我们就扩大。

题目细节：贪心的性质：因为我们想要求 最小值，那么我就应该 按洞的s值从大到小排序，依次来堵住。因为sum为现在没有被堵住的横截面积，我们想要a*S0/sum尽可能大，那就sum减的数值大一点。

具体代码+注释：

#include <queue>
#include <cstdio>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#define PI 3.1415926535898
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+5;
const int maxn7=1e7+5;
const ll INF=1e9;
int n;
double A,B;
double a[maxn],b[maxn];
double sum=0;
double fenzi;
bool cmp(double a,double b)
{
    return a>b;
}
bool judge(int x)
{
    double ans=0;
    for(int i=2;i<=x+1;i++)
        ans+=b[i];
    double y=(fenzi)/(double)(sum-ans)*A;
    if(y-B>=0) return true;
    return false;

}
int main()
{
    scanf("%d%lf%lf",&n,&A,&B);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&a[i]);
        b[i]=a[i];
        sum+=a[i];
    }
    fenzi=a[1];
    sort(b+2,b+1+n,cmp);
    int l=0,r=n-1;
    int ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(judge(mid)==true)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

②CodeForce 1117B&&Emotes

题目描述：

There are nn emotes in very popular digital collectible card game (the game is pretty famous so we won't say its name). The ii-th emote increases the opponent's happiness by aiai units (we all know that emotes in this game are used to make opponents happy).

You have time to use some emotes only mm times. You are allowed to use any emotion once, more than once, or not use it at all. The only restriction is that you cannot use the same emote more than kk times in a row (otherwise the opponent will think that you're trolling him).

Note that two emotes ii and jj (i≠ji≠j) such that ai=ajai=aj are considered different.

You have to make your opponent as happy as possible. Find the maximum possible opponent's happiness.

Input

The first line of the input contains three integers n,mn,m and kk (2≤n≤2⋅1052≤n≤2⋅105, 1≤k≤m≤2⋅1091≤k≤m≤2⋅109) — the number of emotes, the number of times you can use emotes and the maximum number of times you may use the same emote in a row.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is value of the happiness of the ii-th emote.

Output

Print one integer — the maximum opponent's happiness if you use emotes in a way satisfying the problem statement.

Examples

Input

6 9 2
1 3 3 7 4 2

Output

54

Input

3 1000000000 1
1000000000 987654321 1000000000

Output

1000000000000000000

题目大意：有一堆表情，每个表情都有一个权值，每次对每个表情的使用不加限制，不过不可以连续使用k次这个表情，问使用n次表情，最多可以获得多大权值？

题目思路：这个题算是这套题里，最水的了：因为不能连续使用k次我们就连续使用k次，然后第k+1次我们使用权值第二大的，以此为一个循环，最后输出就好啦。

具体注释+代码：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#define PI 3.1415926535898
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+5;
const int maxn7=1e7+5;
const ll INF=1e9;
ll n,m,k;
ll num[maxn];
bool cmp(ll a,ll b)
{
    return a>b;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&num[i]);
    sort(num+1,num+1+n,cmp);
    ll sum=k*num[1]+num[2];//循环
    k++;
    ll res=m%k;
    ll cir=m/k;
    printf("%lld\n",cir*sum+res*num[1]);
    return 0;
}

其实排序也不需要，可以用之前说过的记录最大值和次大值的思想。

③POJ2992&&Divisors

题目描述：

Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?

Input

The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.

Output

For each instance, output a line containing exactly one integer -- the number of distinct divisors of Cnk. For the input instances, this number does not exceed 2 63 - 1.

Sample Input

5 1
6 3
10 4

Sample Output

2
6
16

题目大意：求组合数 C(n,k)的因子数。

题目思路：这道题看似很简单，其实不然，我之前是想：

第一步：杨辉三角组合数打表    第二步：直接分解这个数判断因子就可以。

结果超时了，我又把循环优化到431还是 TLE，所以这个方法行不通。

过了一天，受到同学的启发，我们可以事先打表，把n的阶乘都分解出来，n的阶乘 对应的质数分解，质数的幂记录一下，到最后我们只需要根据公式 指数运算是一个相减的运算，减后的结果 +1相乘求得因子数就好，最大复杂度 O（400）

具体代码+注释：

#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
bool vis[1500];
int prime[1500];
ll cnt=0;
int num[455][455];
void set_prime()//素数打表
{
    memset(vis,false,sizeof(vis));
    for(int i=2;i<1005;i++)
    {
        if(vis[i]==false) prime[++cnt]=i;
        for(int k=1;k<=cnt&&i*prime[k]<1005;k++)
        {
            vis[i*prime[k]]=true;
            if(i%prime[k]==0)
                break;
        }
    }
}
void N_div(int x)//阶乘分解
{
    for(int i=2;i<=x;i++)
    {
        int z=i;
        for(int k=1;k<=cnt&&prime[k]*prime[k]<=z;k++)
        {
            while(z%prime[k]==0)
            {
                num[x][prime[k]]++;
                z/=prime[k];
            }
        }
        if(z>1) num[x][z]++;
    }
}
void start()//把每一个数的阶乘对应的 质数幂都存起来
{
    for(int i=2;i<=450;i++)
        N_div(i);
}
int main()
{
    int n,m,k;
    set_prime();
    start();
    while(~scanf("%d%d",&n,&k))
    {
        ll sum=1;
        for(int i=1;i<=cnt&&prime[i]<=455;i++)//模拟指数相减运算
            sum*=(num[n][prime[i]]-num[k][prime[i]]-num[n-k][prime[i]])+1;
        printf("%lld\n",sum);
    }
    return 0;
}

④Ehab and a 2-operation task&&CodeForce1088C

题目描述：

You're given an array aa of length nn. You can perform the following operations on it:

• choose an index ii (1≤i≤n)(1≤i≤n), an integer xx (0≤x≤106)(0≤x≤106), and replace ajaj with aj+xaj+x for all (1≤j≤i)(1≤j≤i), which means add xx to all the elements in the prefix ending at ii.
• choose an index ii (1≤i≤n)(1≤i≤n), an integer xx (1≤x≤106)(1≤x≤106), and replace ajaj with aj%xaj%x for all (1≤j≤i)(1≤j≤i), which means replace every element in the prefix ending at ii with the remainder after dividing it by xx.

Can you make the array strictly increasing in no more than n+1n+1 operations?

Input

The first line contains an integer nn (1≤n≤2000)(1≤n≤2000), the number of elements in the array aa.

The second line contains nn space-separated integers a1a1, a2a2, ……, anan (0≤ai≤105)(0≤ai≤105), the elements of the array aa.

Output

On the first line, print the number of operations you wish to perform. On the next lines, you should print the operations.

To print an adding operation, use the format "11 ii xx"; to print a modding operation, use the format "22 ii xx". If ii&nbs***bsp;xx don't satisfy the limitations above, or you use more than n+1n+1 operations, you'll get wrong answer verdict.

Examples

Input

3
1 2 3

Output

0

Input

3
7 6 3

Output

2
1 1 1
2 2 4

Note

In the first sample, the array is already increasing so we don't need any operations.

In the second sample:

In the first step: the array becomes [8,6,3][8,6,3].

In the second step: the array becomes [0,2,3][0,2,3].

题目大意：你有两种操作：第一种操作，你可以把1-x范围内都加上一个数，第二种操作，你可以把1-x范围内都对一个数取余。

输出在n+1步之内，使得这个序列变得严格的递增。

题目思路：刚读完完全懵逼，然后最后才做的这个题，没想到这么简单，这种是构造题，对于思维培养比较好，接下来提供两种思路：

第一种：第一步对 1-n的数都加上一个巨大的数，随后的n步每次 到从1-i对num[i]-i+1取余，此时num[1]变成了0，num[2]变成了1，这里没必要考虑 num[1]对取余的影响我们期初已经把这个数变的非常大了，所以最后可以使得序列变成严格递增。

具体代码：(第一种思路)

int num[maxn];

int main()
{
    int n;
    int cas=0;
    int w=5e5+10;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        num[i]+=w;
    }
    printf("%d\n",n+1);
    printf("%d %d %d\n",++cas,n,w);
    for(int i=1;i<=n;i++)
        printf("2 %d %d\n",i,num[i]-i+1);
    return 0;
}

⑤String Problem&&CodeForce 33B

题目描述：

Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change onearbitrary character Ai in one of the strings into arbitrary character Bi, but he has to pay for every move a particular sum of money, equal to Wi. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings.

Input

The first input line contains two initial non-empty strings s and t, consisting of lower case Latin letters. The length of each string doesn't exceed 105. The following line contains integer n (0 ≤ n ≤ 500) — amount of possible changings. Then follow n lines, each containing characters Ai and Bi (lower case Latin letters) and integer Wi (0 ≤ Wi ≤ 100), saying that it's allowed to change character Ai into character Bi in any of the strings and spend sum of money Wi.

Output

If the answer exists, output the answer to the problem, and the resulting string. Otherwise output -1 in the only line. If the answer is not unique, output any.

Examples

Input

uayd
uxxd
3
a x 8
x y 13
d c 3

Output

21
uxyd

Input

a
b
3
a b 2
a b 3
b a 5

Output

2
b

Input

abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0

Output

-1

题目大意：有两个字符串，接下来提供 每个字母之间的转换关系，每对字母转换时都有一个权值，问转化成相同字符串时最小权值是多少，并输出该相同的字符串。

题目思路：是一个最短路的转换题，可以把字母与字母之间的权值对应成边，如果两个字符串某个位置不相同，算出这两个字母可以同时转换成哪个字母并且权值最小，把该字母记录到数组里即可。

具体细节：

1.不一定是 1-2 2-1这样转换 还有可能1-3,2-3都变成3也可以

2.不一定非要1-2 也可以1-3-2，这样也是可以的

3.长度不相等时一定没办法相同||当两个字母无法都转成另一个字母或者两个字母不能对应转换时一定没办法相同

4.实现根据边都把 数据储存到 一个数组dis[s][]中，第一维代表该字母，其余的代表该字母能够转换到另一个字母时的最小权值

5.输入边的权值时记录的最小的

具体代码+注释：

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
char str1[maxn];
char str2[maxn];
int n;
int tel[1005][1005];
struct node{
    int e,w,next;
}edge[maxn];
ll cnt=1;
int dis[30][30];
int head[1005];
bool vis[30];
char cop[maxn];
void restart()
{
    memset(tel,0,sizeof(tel));
    memset(head,-1,sizeof(head));
    cnt=1;
}
void addedge(int u,int v,int w)
{
    tel[u][v]=cnt;
    edge[cnt]=node{v,w,head[u]};
    head[u]=cnt++;
}
void spfa(int s)//最短路更新
{
    for(int i=1;i<=26;i++) dis[s][i]=INF,vis[i]=false;
    queue<int>q;q.push(s);
    vis[s]=true;dis[s][s]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=false;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dis[s][e]>dis[s][u]+edge[i].w)
            {
                dis[s][e]=dis[s][u]+edge[i].w;
                if(vis[e]==false)
                {
                    q.push(e);
                    vis[e]=true;
                }
            }
        }
    }
}

int main()
{
    restart();
    scanf("%s%s",str1+1,str2+1);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        char s1[5],s2[5];int w;
        scanf("%s%s%d",s1,s2,&w);
        int temp1=s1[0]-96,temp2=s2[0]-96;

        if(tel[temp1][temp2])//要每次更新最短距离
        {
            int index=tel[temp1][temp2];
            edge[index].w=min(edge[index].w,w);
        }
        else
            addedge(temp1,temp2,w);
    }
    int len1=strlen(str1+1),len2=strlen(str2+1);
    if(len1!=len2) printf("-1\n");
    else
    {
        ll sum=0,flag=0;
        for(int i=1;i<=26;i++)
            spfa(i);//都储存好每个点到每个点的最小距离
        for(int i=1;i<=len1;i++)
        {
            int minl=INF;
            if(str1[i]!=str2[i])
            {
                int s=str1[i]-96,s2=str2[i]-96;
                int cho;
                for(int j=1;j<=26;j++)
                {
                    if(minl>dis[s][j]+dis[s2][j])//擂台法比较出最小值，并且记录该字母
                    {
                        minl=dis[s][j]+dis[s2][j];
                        cho=j;
                    }
                }
                if(minl>=INF) {flag=1;break;}
                cop[i]=cho+96;
                sum+=minl;
            }
            else
                cop[i]=str1[i];
        }
        if(flag) printf("-1\n");
        else
        {
            printf("%lld\n",sum);
            printf("%s\n",cop+1);
        }
    }
    return 0;
}

⑥POJ1804&&Brainman

题目描述：

Background 
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task. 

Problem 
Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example: 

Start with: 2 8 0 3 
swap (2 8) 8 2 0 3 
swap (2 0) 8 0 2 3 
swap (2 3) 8 0 3 2 
swap (8 0) 0 8 3 2 
swap (8 3) 0 3 8 2 
swap (8 2) 0 3 2 8 
swap (3 2) 0 2 3 8 
swap (3 8) 0 2 8 3 
swap (8 3) 0 2 3 8

So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps: 

Start with: 2 8 0 3 
swap (8 0) 2 0 8 3 
swap (2 0) 0 2 8 3 
swap (8 3) 0 2 3 8

The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.

Input

The first line contains the number of scenarios. 
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

Output

Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.

Sample Input

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

Sample Output

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

题目大意：给你一个序列，问至少要交换多少次，使得该序列有序。两种做法：

第一种：过程模拟冒泡排序或者选择排序，如果交换一次，次数就相应++。(不过只使用与这个题，因为这个题给的数据范围太小，因为冒泡排序是n^2的复杂度)

第二种：树状数组求逆序数(nlgn)：

首先将数据离散化(因为出现负数没办法进行标记啦)，只要出现一次该数就++，然后统计大于该数的现在出现了多少次就可以了

我用的树状数组，具体代码+注释：

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
struct node{
    int id,val;
}inn[maxn];
int noorder[maxn];
int n;
bool cmp(node a,node b)
{
    if(a.val==b.val)
        return a.id<b.id;
    return a.val<b.val;
}
ll sum[maxn];
void update(int x,int w)//单点更新
{
    for(;x<=n;x+=(x&-x))
        sum[x]+=w;
}
int ask(int x)//单点查询
{
    int res=0;
    for(;x>=1;x-=(x&-x))
        res+=sum[x];
    return res;
}
int quuery(int l,int r)//查询区间
{
    return ask(r)-ask(l-1);
}
int main()
{
    int T;
    scanf("%d",&T);
    int cas=0;
    int flag=0;
    while(T--)
    {
        if(!flag) flag=1;
        else printf("\n");
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&inn[i].val);
            inn[i].id=i;
        }
        sort(inn+1,inn+1+n,cmp);
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
            noorder[inn[i].id]=i;
        ll cnt=0;
        for(int i=1;i<=n;i++)
        {
            cnt+=quuery(noorder[i],n);
            update(noorder[i],1);
        }
        printf("Scenario #%d:\n%lld\n",++cas,cnt);
    }
    return 0;
}

⑦HDU1257&&最小拦截系统

题目描述：

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统. 

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔) 

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统. 

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

2

题目大意：中文题相信你们

题解思路：这是一个模拟性质的题目，我们只需要根据 拦截系统 的性质判断一下 全拦下最小需要多少个就可以了。

具体细节：不是在求有多少个连续单调递减序列，有可能 下一个虽然比现在的高度要 高(拦不下了)，但是此时可能无需再增加一个拦截系统，因为前面有可能最后的高度比这个高。所以我们根据这个序列模拟一下这个过程就好了，我们从一个数开始把比他低的都标记为-1，cnt++，然后再从第二个不是-1的开始，比他低的都标记为-1，就这样下去最后结果就是最小的

具体代码：

const int maxn=1e6+5;
const int maxn7=1e7+5;
const ll INF=1e9;
ll n,m,k;
int num[maxn];
ll cnt=0;
int vis[maxn];
int main()
{
    while(~scanf("%lld",&n))
    {
        cnt=0;
        for(int i=1;i<=n;i++)
            scanf("%lld",&num[i]);
        for(int i=1;i<=n;i++)
        {
            if(num[i]!=-1)
            {
                ll now=num[i];
                num[i]=-1;
                for(int k=i+1;k<=n;k++)
                {
                    if(now>num[k]&&num[k]!=-1)
                    {
                        now=num[k];
                        num[k]=-1;
                    }
                }
                cnt++;
            }
        }
        printf("%lld\n",cnt);
    }
    return 0;
}

⑧New Year and the Sphere Transmission&&CodeForce-1091C

题目描述：

here are nn people sitting in a circle, numbered from 11 to nn in the order in which they are seated. That is, for all ii from 11 to n−1n−1, the people with id ii and i+1i+1 are adjacent. People with id nn and 11 are adjacent as well.

The person with id 11 initially has a ball. He picks a positive integer kk at most nn, and passes the ball to his kk-th neighbour in the direction of increasing ids, that person passes the ball to his kk-th neighbour in the same direction, and so on until the person with the id 11 gets the ball back. When he gets it back, people do not pass the ball any more.

For instance, if n=6n=6 and k=4k=4, the ball is passed in order [1,5,3,1][1,5,3,1].

Consider the set of all people that touched the ball. The fun value of the game is the sum of the ids of people that touched it. In the above example, the fun value would be 1+5+3=91+5+3=9.

Find and report the set of possible fun values for all choices of positive integer kk. It can be shown that under the constraints of the problem, the ball always gets back to the 11-st player after finitely many steps, and there are no more than 105105 possible fun values for given nn.

Input

The only line consists of a single integer nn (2≤n≤1092≤n≤109) — the number of people playing with the ball.

Output

Suppose the set of all fun values is f1,f2,…,fmf1,f2,…,fm.

Output a single line containing mm space separated integers f1f1 through fmfm in increasing order.

Examples

Input

6

Output

1 5 9 21

Input

16

Output

1 10 28 64 136

Note

In the first sample, we've already shown that picking k=4k=4 yields fun value 99, as does k=2k=2. Picking k=6k=6 results in fun value of 11. For k=3k=3 we get fun value 55 and with k=1k=1&nbs***bsp;k=5k=5 we get 2121.

In the second sample, the values 11, 1010, 2828, 6464 and 136136 are achieved for instance for k=16k=16, 88, 44, 1010and 1111, respectively.

题目描述：问从1开始又回到1，每次跳跃步数不同，回到1之后会有几种权值，拿6来说

一次跳一步 1 2 3 4 5 6 权值=21

一次跳二步 1 3 5 1 权值=9

像这样一共可以产生1 5 9 21四种权值并输出。

题目思路：

1.首先，如果我们每次跳的是n的因子数，那么他绝对可以跳回1，然而如果不是k的因子数呢？

2.我们列一下方程，如果一个数跳x步，每次跳k，要回到一个点p，那么我们可以列出当前的同余方程xk=p(mod n) 所以xk+yn=p，当且仅当p/gcd(k,n)时有解。

3.也就是说p必须是gcd(k,n)的倍数，所以这个p为多少呢，因为k的范围是1-n所以GCD(n,k)只能是 n的因子，不妨列一列试试。

所以p只能是 n的因子 跳跃的 位置，所以说无论 k取多少，最后都有 n的因子数种情况，所以我们把 n的因子数都求出来，用等差数列求和公式求一下就可以了！！

具体代码+注释：

ll n;

ll calculate(ll x)
{
    ll ans=n/x;
    ll sum=(ans*x+2-x)*ans/2;
return sum;
}
int main()
{
    scanf("%lld",&n);
    set<ll>s;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            ll ans;
            ans=calculate(i);
            s.insert(ans);
            ans=calculate(n/i);
            s.insert(ans);
        }
    }

    for( set<ll>::iterator it=s.begin();it!=s.end();it++)
        printf("%lld ",*it);
    return 0;
}

set是去重自动排序的一个STL容器，需要迭代器进行遍历，如果不会使用(我也是现搜的迭代器)，可以把所有的数都放到数组里最后排序输出就好啦。

⑨QS-network&&ZOJ1586

题目描述：

Sunny Cup 2003 - Preliminary Round

April 20th, 12:00 - 17:00

Problem E: QS Network

In the planet w-503 of galaxy cgb, there is a kind of intelligent creature named QS. QScommunicate with each other via networks. If two QS want to get connected, they need to buy two network adapters (one for each QS) and a segment of network cable. Please be advised that ONE NETWORK ADAPTER CAN ONLY BE USED IN A SINGLE CONNECTION.(ie. if a QS want to setup four connections, it needs to buy four adapters). In the procedure of communication, a QS broadcasts its message to all the QS it is connected with, the group of QS who receive the message broadcast the message to all the QS they connected with, the procedure repeats until all the QS's have received the message.

A sample is shown below:

A sample QS network, and QS A want to send a message.

Step 1. QS A sends message to QS B and QS C;

Step 2. QS B sends message to QS A ; QS C sends message to QS A and QS D;

Step 3. the procedure terminates because all the QS received the message.

Each QS has its favorate brand of network adapters and always buys the brand in all of its connections. Also the distance between QS vary. Given the price of each QS's favorate brand of network adapters and the price of cable between each pair of QS, your task is to write a program to determine the minimum cost to setup a QS network.

Input

The 1st line of the input contains an integer t which indicates the number of data sets.

From the second line there are t data sets.

In a single data set,the 1st line contains an interger n which indicates the number of QS.

The 2nd line contains n integers, indicating the price of each QS's favorate network adapter.

In the 3rd line to the n+2th line contain a matrix indicating the price of cable between ecah pair of QS.

Constrains:

all the integers in the input are non-negative and not more than 1000.

Output

for each data set,output the minimum cost in a line. NO extra empty lines needed.

Sample Input

1
3
10 20 30
0 100 200
100 0 300
200 300 0

Sample Output

370

题目大意：每个点都有一个权值，没两个点之间有一条边也有权值，毎连起这两个点就会 需要两个点的权值 +这条边的权值，意思就是 假如链接了ab那么sum+=a的权值+b的权值+ab之间的权值，又链接bc sum+=b的权值+c的权值+bc之间的权值。意思就是点的权值必须要重复加。

题目思路：最小生成树的一个变式，我们把点的权值都融进到边的权值当中，这个题就变得很简单了，就是一个模板题啦。

所以具体代码+注释：

const int maxn3=1e3+5;

const int maxn=1e6+5;

int n;

int mp[maxn3][maxn3];
int pre[maxn];
int num[maxn];
struct node{
    int s,e,w;
}edge[maxn];
void restart()
{
    for(int i=0;i<maxn;i++)
        pre[i]=i;
}
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int Find(int x)
{
    return pre[x]==x?x:Find(pre[x]);
}
bool Merge(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy)
    {
        pre[fx]=fy;
        return true;
    }
    return false;
}
int main()
{
    int T; ll cnt=0;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        restart();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        for(int i=1;i<=n;i++)
            for(int k=1;k<=n;k++)
                scanf("%d",&mp[i][k]);
        for(int i=1;i<=n;i++)
        {
            for(int k=1;k<=i;k++)
            {
                if(i==k) continue;
                edge[++cnt]=node{i,k,mp[i][k]+num[i]+num[k]};
            }
         }
         sort(edge+1,edge+1+cnt,cmp);
         ll res=0,ans=0;
         for(int i=1;i<=cnt&&res<=n-1;i++)
         {
             int e=edge[i].e,s=edge[i].s;
             if(Merge(s,e)==true)
             {
                res++;
                ans+=edge[i].w;
             }
         }
         if(res>=n-1) printf("%lld\n",ans);
    }
    return 0;
}

⑩Visible Lattice Points&&POJ3090

题目描述：

A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points.

Write a program which, given a value for the size, N, computes the number of visible points (x, y) with 0 ≤ x, y ≤ N.

Input

The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing a single integer N (1 ≤ N ≤ 1000), which is the size.

Output

For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.

Sample Input

4
2
4
5
231

Sample Output

1 2 5
2 4 13
3 5 21
4 231 32549

题目大意：问在 n+1阶的矩阵中，有多少个整数点(x,y)与原点的连线不经过其他点

题目思路：一开始我是把所有的点的都枚举，判断这个斜率k出现过没有，没有出现过就++，这样就可以了，意思就是统计有多少种不同的斜率，因为如果三个点 斜率相同只连最近的一个就不会经过其他两个，所以就是统计斜率k的种数，然而TLE了，后来一想，发现如果这个斜率在此之前没有出现过，那么再次出现的话绝对是以他的倍数出现，比如说3/5，下次出现的话就是6/10，所以这里我们就可以想到，统计每行与他互质的数目，然后*2(因为这只是一半，还有以列为基础)，最后加上中间的点1,1，即答案种数。

所以两种方法：

第一种：求gcd遍历枚举，gcd=1就可以。

第二种：首先欧拉函数打表，因为欧拉函数代表的不就是小于n与n互质的个数吗,最后从oula[1]加到oula[n]就好了。

具体代码+注释：

int n;
int oula[maxn];

int prime[maxn];

bool vis[maxn];

ll cnt=0;
void set_oula()
{
    memset(vis,false,sizeof(vis));
    for(int i=2;i<maxn;i++)
    {
        if(vis[i]==false) prime[++cnt]=i,oula[i]=i-1;
        for(int k=1;k<=cnt&&i*prime[k]<maxn;k++)
        {
            vis[i*prime[k]]=true;
            if(i%prime[k]==0)
            {
                oula[i*prime[k]]=oula[i]*prime[k];
                break;
            }
            oula[i*prime[k]]=oula[i]*oula[prime[k]];
        }
    }
}
int main()
{
    set_oula();
    int T;scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        scanf("%d",&n);
        ll sum=0;
        oula[1]=1;
        for(int i=1;i<=n;i++)
            sum+=oula[i];
        printf("%d %d %lld\n",++cas,n,2*sum+1);
    }
    return 0;
}

然后这套题就结束了，具体总结一下呢，就是思维的问题，一些问题需要通过转换，别把自己当成死木头似的不动，还有不要骄傲，有了思路不一定对，还是需要细心，细心加细心，一步步的就会ac，然后希望同大家一起进步！加油！