P6485 [COCI2010-2011#4] PROSJEK 题目解析

· · 题解

更好的阅读体验

题目传送门

算法描述：

一道数学题。

输入的是一个小数，是一个平均数，但是这样来凑数字就会变得非常麻烦，于是我们需要把这个平均数变成整数，把问题变成：你要选一堆数，让它们的和变成给你的整数。

变成整数的话，就需要不断地乘 10，需要乘 10^a，其中，a 为小数的位数。

然后就可以枚举了，设这个平均数的整数部分为 x，那么就用 x 和 x+1 来组成这个数。

随后我们要求出总个数，然而，总个数即这个 10^a，和这个变成整数的平均数的最大公因数。显然， 10^a 只含有质因子 2 和 5。所以我的代码里面只有判断除以 2 和 5。

随后，我们先假设这个数全部都由 x 来组成（上面提到的），但是这样肯定会少，少多少呢，就是少这个小数的小数部分组成的数，比如说 3.114514，小数部分就是 114514，然后我们把它少的部分全部替换成 x+1，剩下的就是 x 了。

代码：

#include<bits/stdc++.h>
using namespace std;
string s;int a=1,b=0,ans=0,l,r;
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(i!=1)b=b*10+s[i]-'0'; // 转换成整数
        if(i>1)a*=10,ans=ans*10+s[i]-'0'; //计算出小数位数和不断乘 10
    }
    while(b%2==0&&a%2==0){b/=2;a/=2;ans/=2;}
    while(b%5==0&&a%5==0){b/=5;a/=5;ans/=5;} //除上最大公因数
    l=s[0]-'0';r=l+1; //计算出 x 和 x+1
    if(l==5){cout<<"0 0 0 0 1"<<endl;return 0;} //特判
    for(int i=1;i<=5;i++){
        if(i==1){
            if(l==1)cout<<a-ans;
            else cout<<0;
        }else{
            if(l==i)cout<<" "<<a-ans;
            else if(r==i)cout<<" "<<ans;
            else cout<<" "<<0;
        }
    }cout<<endl;
    return 0;
}