Article From:https://www.cnblogs.com/lllxq/p/9967752.html

Contents

### Problem G: Approximate Research

Time limit: 1 SecMemory limit: 128 MB

Submission: 30Solution: 25

[Submit [status] discussion [proposer:admin]

#### Title Description

Scientists’explorations on the planet Samuel have been enriched with energy reserves, making it possible for the long-term operation of the large computer “Samuel II” on the space station. As a result of last year’s hard work and good results, the League was allowed to use “Samuel II”Mathematical research.

Xiaolian recently studied the problem of approximation. He counted the number of approximations of each positive number N and expressed it in F (N). For example, the approximate number of 12 is 1, 2, 3, 4, 6, 12. So f (12) =6. The following table gives some values of f(N):

Now the League hopes to use “Samuel II” to count the sum of F (1) to f (N) and M.

Xiaolian recently studied the problem of approximation. He counted the number of approximations of each positive number N and expressed it in F (N). For example, the approximate number of 12 is 1, 2, 3, 4, 6, 12. So f (12) =6. The following table gives some values of f(N):

Now the League hopes to use “Samuel II” to count the sum of F (1) to f (N) and M.

#### input

Only one line and one integer N (0< N< 1000000)

#### output

There is only one line of output, which is the sum of integers M, i. e. f (1) to f (N).

#### sample input

```
3
```

#### sample output

5

Train of thought:

1.The rule of tabulation: f[x]=(num_of {prime_fac[i]}+1)

2.The contribution of approximate number I to the answer is N/i ans = sum (N/i)

ACCode:

#include <iostream> #include<cstdio> #include<cmath> typedef long long ll; using namespace std; bool isprime[1000010]; ll cnt=0,prime[1000010]; ll num[1000010]; void get_prime(){ for(int i=0;i<=1000000;i++) isprime[i]=1; isprime[0]=isprime[1]=0; for(ll i=2;i<=1000000;i++){ if(isprime[i]) { prime[++cnt]=i;num[i]=2; for(ll j=i+i;j<=1000000;j+=i) { isprime[j]=0; ll tmp=0,cop=j; while(cop%i==0) cop/=i,tmp++; num[j]*=(tmp+1); } } } } int main() { for(ll i=0;i<=1000000;i++) num[i]=1; get_prime(); ll n;scanf("%lld",&n); ll ans=0; for(ll i=1;i<=n;i++){ ans+=num[i]; } printf("%lld\n",ans); return 0; }

### Question D: shuffle

Time limit: 1 SecMemory limit: 128 MB

Submission: 18Solution: 14

[Submit [status] discussion [proposer:admin]

#### Title Description

In recognition of Xiaolian’s contribution to the exploration of Samuel, Xiaolian was invited to participate in the close manned exploration of Samuel. Because the planet Samuel is so far away that scientists have to spend quite a long time in the spaceship, Xiaolian proposes to use poker cards to travel long distances.The boredom of time. After playing a few games, people thought that simply playing cards was too easy for a highly intelligent businessman like them. A new method of playing cards has been proposed. A shuffle of playing cards is defined as dividing a stack of N (even N) cards into upper and lower stacks on average.Take the first sheet of the following stack as the first sheet of the new stack, then take the first sheet of the upper stack as the second sheet of the new stack, and then take the second sheet of the next stack as the third sheet of the new stack… So alternate until all cards are finished. For a stack of six cards, 12,3456. The process of shuffling is as follows:

As can be seen from the figure, after a shuffle, the sequence 123,4456 changed to 415,263. Of course, a shuffle of the resulting sequence will turn to 246 135. The game is like this, if given a stack of poker cards of length N, and the cardsFace size increases continuously from 1 to N (regardless of color). For such a stack of poker cards, M shuffles are performed. The first scientist to tell the size of the L card in the shuffled poker sequence won. Can you help Lenovo win the game?

As can be seen from the figure, after a shuffle, the sequence 123,4456 changed to 415,263. Of course, a shuffle of the resulting sequence will turn to 246 135. The game is like this, if given a stack of poker cards of length N, and the cardsFace size increases continuously from 1 to N (regardless of color). For such a stack of poker cards, M shuffles are performed. The first scientist to tell the size of the L card in the shuffled poker sequence won. Can you help Lenovo win the game?

#### input

There are three integers separated by spaces representing N, M and L (where 0 < N < 10 ^ 10, 0 < M < 10 ^ 10, and N is even).

#### output

One-line output specifies the face size of the playing card.

#### sample input

```
6 2 3
```

#### sample output

6

Thought: Find the law:

N=12The change relation is

1->2->4->8->3->6->12->11->9->5->10->7->1

（i->jRepresents that position I moves to position J after a shuffle.

It can be seen that position x moves to x*2% (N+1) after a shuffle.

So after M shuffles position x will move to x*pow(2,M)%(N+1)

Location x moves M times to position L to find position x

That is to say, the solution of equation x*pow(2,M)%(N+1)=L x

ACCode:

#include <iostream> #include<cstdio> typedef long long ll; using namespace std; ll qpow(ll a,ll b,ll mod){ ll ret=1; while(b){ if(b&1) ret=ret*a%mod; a=a*a%mod; b>>=1; } return ret; } void exgcd(ll a,ll b,ll& d,ll& x,ll& y){ if(!b){ d=a; x=1; y=0;} else{ exgcd(b,a%b,d,y,x); y-=x*(a/b); } } int main() { ll n,m,l; scanf("%lld%lld%lld",&n,&m,&l); if(n==1) {printf("1\n"); return 0;} ll a=qpow(2,m,n+1); ll b=(n+1); //printf("a=%lld b=%lld\n",a,b); ll d,x,y; exgcd(a,b,d,x,y); x=x*(l/d),y=y*(l/d); //printf("x=%lld y=%lld\n",x,y); ll k=b/d; //printf("%lld\n",k); if(x<=0) x=x+(x/k)*k; if(x>n) x=x-((x-n)/k)*k; while(x<=0) x+=k; while(x>n) x-=k; printf("%lld\n",x); return 0; }

### Question M: gold coins

Time limit: 1 SecMemory limit: 128 MB

Submission: 118Solution: 44

[Submit [status] discussion [proposer:admin]

#### Title Description

There are n people sitting on the round table. Each person has a certain number of gold coins. The total number of gold coins can be divided by n. Everyone can give some gold coins to his neighbours, eventually making the number of gold coins equal for everyone. Your task is to find the minimum number of gold coins that have been transferred.

#### input

The first action integer n (n> = 3), the following N lines each line a positive integer, according to the counter-clockwise order to give each person has the number of gold coins.

3<=N<=100000,Total gold coins & lt; = 10 ^ 9

3<=N<=100000,Total gold coins & lt; = 10 ^ 9

#### output

Minimum number of gold coins to be transferred

#### sample input

```
4
1
2
5
4
```

#### sample output

```
4
```

#### Tips

Let four persons be numbered 1,2,3,4. The third person gives the second person two gold coins (into 1,4,3,4), the second person and the fourth person gives the first person one gold coin respectively.

Train of thought:

Let Xi denote I - & gt; I + 1 gold coin (i + 1 - & gt; I gold coin is - xi)

be

a1+xn-x1=ave;

a2+x1-x2=ave;

...

an+xn-1-xn=ave;

So:

x1=a1-ave+xn;

x2=a1+a2-2*ave+xn;

x3=a1+a2+a3-3*ave+xn;

...

xn-1=a1+a2+..+an-1-(n-1)*ave+xn;

So min {| x1 |+ | x2 |+ | x3 | +... + | xn |}= min {| ave-a1-xn |+ | 2 * ave-a1-a2-xn |+ | (n-1) * ave a1-a2-. - an-1-xn |+ | 0-0Xn|}

ACCode:

#include <iostream> #include<cstdio> #include<cmath> #include<algorithm> typedef long long ll; using namespace std; ll a[100005],c[100005]; int main() { ll n;scanf("%lld",&n); ll sum=0; for(ll i=1;i<=n;i++){ scanf("%lld",&a[i]); sum+=a[i]; } ll ave=sum/n; for(ll i=1;i<=n-1;i++){ c[i]=c[i-1]+(ave-a[i]); } c[n]=0; sort(c+1,c+1+n); ll x=c[(n+1)/2]; ll ans=0; for(int i=1;i<=n;i++){ ans+=abs(c[i]-x); } printf("%lld\n",ans); return 0; }

Link of this Article: [solution]contest 89