hdu 6237 A Simple Stone Game - CSDN博客

文章价值(3) ?
阅读数(497) ?
Problem Description
After he has learned how to play Nim game, Bob begins to try another stone game which seems much easier.

The game goes like this: one player starts the game with N piles of stones. There is ai stones on the ith pile. On one turn, the player can move exactly one stone from one pile to another pile. After one turn, if there exits a number x(x>1) such that for each pile bi is the multiple of x where bi is the number of stone of the this pile now), the game will stop. Now you need to help Bob to calculate the minimum turns he need to stop this boring game. You can regard that 0 is the multiple of any positive number.
?

Input
The first line is the number of test cases. For each test case, the first line contains one positive number N(1N100000), indicating the number of piles of stones.

The second line contains N positive number, the ith number ai(1ai100000) indicating the number of stones of the ith pile.


The sum of N of all test cases is not exceed 5?105.
?

Output
For each test case, output a integer donating the answer as described above. If there exist a satisfied number x initially, you just need to output 0. It's guaranteed that there exists at least one solution.
?

Sample Input
2 5 1 2 3 4 5 2 5 7
?

Sample Output
2 1
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn];
ll sum,ans,tp1,tp2,tp3;
queue que;
vector nm;
void del(ll n)
{
    for(ll i=2;i*i<=n;i++)
        if((!(n%i))&&(n>=i))
        {
            while(!(n%i))
                n/=i;
            que.push(i);
        }
    if(n!=1)
        que.push(n);
}
int main()
{
    int t,n,i;
    scanf("%d",&t);
    while(t--&&scanf("%d",&n)!=EOF)
    {
        for(sum=0,i=0;i::iterator it=(nm.end()-1);it>=nm.begin();it--)
            {
                tp3+=tp1-*it;
                tp2-=tp1;
                if(tp2<=0)
                    break;
            }
            ans=min(ans,tp3);
        }
        printf("%lld\n",ans);
    }
    return 0;
}





(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: