NIO's Sword

题目描述

See Problem N for PDF statements.

NIO is playing a new game. In this game, NIO has a sword with attack power represented by an integer AAA. Initially, A=0A=0A=0. There are also nnn enemies in the game. NIO has to kill them in order, which means NIO must kill the (i−1)(i-1)(i−1)-th enemy before killing the iii-th enemy for each iii (2≤i≤n2\le i\le n2≤i≤n). For the iii-th enemy, NIO can kill it if and only if A≡i(modn)A\equiv i \pmod{n}A≡i(modn).

Fortunately, NIO can upgrade his sword at any moment for any number of times. Each time NIO upgrades his sword, he first chooses an integer xxx (0≤x≤90\le x\le 90≤x≤9), then changes the attack power of the sword from AAA to 10×A+x10\times A+x10×A+x.

NIO wants to minimize the number of times to upgrade the sword so that he can win the game as fast as possible. Can you help him to find the minimum times?

输入描述:

The first line contains one integer nnn (1≤n≤1061\le n\le 10^{6}1≤n≤106), indicating the number of enemies.

输出描述:

Output one integer indicating the minimum times to upgrade the sword.

示例1

输入

4

输出

4

说明

Here is a possible solution for the example:

- The attack power of the sword when killing the first enemy can be 10×0+1=110\times0+1=110×0+1=1.
- The attack power of the sword when killing the second enemy can be 10×1+4=1410\times1+4=1410×1+4=14.
- The attack power of the sword when killing the third enemy can be 10×14+7=14710\times14+7=14710×14+7=147.
- The attack power of the sword when killing the fourth enemy can be 10×147+2=147210\times147+2=147210×147+2=1472.

So he needs to upgrade the sword at least four times.

思路：

1，关于余数，13%3==1,12%3==132%3==0,所以只需要看余数，las记载上次的余数

2，参看

 

代码：

#include
using namespace std;
#define int long long//考察余数，距离，数组的运用
const int maxj=1e6+100;
int p10[300];
int num[maxj];
signed main(){
    int n;
    cin>>n;
    p10[0]=1;
    if(n==1){
        cout<<0<<'\n';
        return 0;
    }
    for(int i=1;i<=16;++i){
        p10[i]=p10[i-1]*10;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        int las=i-1;//上次的余数
        for(int j=1;j<16;++j){
            int k=((i-p10[j]*las)%n+n)%n;//看相对于n而言，与i的距离
            if(k//在pow（10，j）内可以满足
                ans+=j;
                break;
            }
        }
    }
    cout<'\n';
    return 0;
}

Particle Arts

题目描述

In a confined NIO space, there are nnn NIO particles, the iii-th of which has aia_iai​ joule energy. The NIO particles are very special as they keep colliding with each other randomly. When one particle carrying energy aaa joule collides with another particle carrying energy bbb joule, they will be annihilated and produce two new particles carrying the energy of a AND ba\ \texttt{AND}\ ba AND b and a OR ba\ \texttt{OR}\ ba OR b respectively. Here AND\texttt{AND}AND and OR\texttt{OR}OR mean bitwise AND and OR operation respectively.

The variance of the energy of these particles is obviously not decreasing, but unfortunately, the space here is too small for the author to write down his proof. After enough time the variance of the energy of these particles converges to a stable value. Can you find this value?

The variance of nnn numbers is defined as follows.

σ2=1n∑i=1n(xi−μ)2where μ=1n∑i=1nxi

σ2where μ​=n1​i=1∑n​(xi​−μ)2=n1​i=1∑n​xi​​

输入描述:

The first line contains an integer nnn (2≤n≤1052\le n\le 10^52≤n≤105), indicating the number of particles.

The second line contains nnn integers a1,a2,…,ana_1,a_2,\ldots, a_na1​,a2​,…,an​ (0≤ai<2150\le a_i < 2^{15}0≤ai​<215), indicating the enegery of the particles.

输出描述:

Output a irreducible fraction ab\dfrac{a}{b}ba​ (b>0b > 0b>0) in the form of a/b\texttt{a/b}a/b that represents the answer. You should ensure that gcd⁡(a,b)=1\gcd(a,b) = 1gcd(a,b)=1 or when a=0a=0a=0, bbb should be 111.

示例1

输入

5
1 2 3 4 5

输出

54/5

备注:

Warm tip: Please note the use of data types.

思路：

最后的状态是和不变

按转化为二进制，然后转化为最大到最小十进制

代码：

#include
using namespace std;
#define int __int128
#define vec vector
#define rep(i,l,r) for(int i=l;i<=r;++i)
#pragma GCC optimize(2)//
#pragma GCC optimize(3,"Ofast","inline")//
const int maxj=2e5+100,mod=1e9+7,nn=33554432;
int ksm(int a,int b){//快速幂
    int ans=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
void read(__int128 &x){
    x=0;
    int f=1;
    char ch;
    if((ch=getchar())=='-')f=-f;
    else x=x*10+ch-'0';
    while((ch=getchar())<='9'&&ch>='0')x=x*10+ch-'0';
    x*=f;   
}
void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)print(x/10);
    putchar(x%10+'0');
    
}
int wi[100100];
int a[maxj];
void solve(){
    int n;
    read(n);
    for(int i=1;i<=n;++i){//终态与二进制有关
        int x;
        read(x);
        int t=0;
        while(x){
            if(x&1)wi[t]++;
            x>>=1;
            t++;
        }
    }
    int sum=0;
    for(int i=1;i<=n;++i){
        a[i]=0;
        int t=0,ww=1;
        for(int j=0;j<=62;++j){
            if(wi[j]){
                t+=ww;
                wi[j]--;
            }
            ww*=2;
        }   
        a[i]=t;
        sum+=t;
    }
    int m=n;
    if(sum==0){
        cout<<0<<'/'<<1<<'\n';
        return ;
    }
    int temp=sum;
    sum/=__gcd(sum,m);
    n/=__gcd(temp,n);
    int ans=0;
    for(int i=1;i<=m;++i){
        ans=ans+(sum-a[i]*n)*(sum-a[i]*n);//算方差，不太一样
    }
    int k=m*n*n;//分母
    int ss=k;
    k/=__gcd(k,ans);
    ans/=__gcd(ans,ss);
    
    print(ans);
    cout<<'/';
    print(k);
}
signed main(){
    int t;
    // cin>>t;
    t=1;
    while(t--)solve();
    return 0;
}