The 30th day of question brushing

I did three pen tests today ... It's so hard

1. Choose an inn

Lijiang River has n It's a unique inn , The inn is in the order of its location 1 To n Number . Every inn is decorated in a certain tone （ in total k Kind of , Integers 0∼k−1 Express ）, And every inn has a coffee shop , Each coffee shop has its own minimum consumption .
The two tourists went to Lijiang for a tour , They like the same color , I want to try two different Inns , So I decided to stay in two Hotels with the same color . evening , They are going to choose a coffee shop for coffee , The coffee shop is required to be located between the two inns where two people live （ Including their inn ）, And the minimum consumption of coffee shops shall not exceed p.

They want to know how many options there are for accommodation , Ensure that you can find one at night with a minimum consumption of no more than p Yuan coffee shop small gathering .

Input

• The first row has three integers n,k,p, Every two integers are separated by a space , Each represents the number of inns , The number of tones and the highest value of the lowest acceptable consumption ;
• Next n That's ok , The first i+1 Line two integers , Separated by a space , respectively i The decorative tone and... Of the No. inn i The minimum consumption of the coffee shop at the No. 1 Inn .

Output

• There is only one line of output , An integer , Indicates the total number of alternative accommodation options .

analysis ：

Simulate according to the requirements of the topic , Choose two at a time to judge , If the following conditions are met ：

• The colors of the two inns are the same
• Between the two Inns （ Including two Inns ） There is a coffee shop in which the minimum consumption is less than or equal to p Is a solution that satisfies the condition

For every inn , Consider pairing with the inn in front of the current point . Preprocessing pre Express i spot （ contain i spot ） The first one in front <=p The inn of . For every color , Find out sum Before presentation i How many points have the same color as the current enumeration . Enumerate each inn in turn , If the current minimum consumption of the inn <=p, The current Inn can be matched with any Inn in front , also pre It must be equal to i, So the answer can be accumulated sum[pre]-1; For the current minimum consumption of the inn >p, Then the current Inn can only be with pre And the previous Inn , So the answer can be accumulated sum[pre].

Simulation process ：

• Find the first point that meets the consumption requirements , So the previous record color All in sum, such , As long as there is color The same thing , More sum There are two accommodation schemes （ to update ans）, here , The front color Clear it all .
• Find the second point that meets the consumption requirements , Then between two points color All in sum（ Write it down as sum（ new ））, such , As long as there is color The same thing , So much sum（ new ） There are two accommodation schemes （ to update ans）, here color Reset again , Then the same goes for .

#include<stdio.h>
const int MX=200001;
int cnt[MX],last[MX],sum[MX],n,k,p,now;

int main()
{
    
    int ans=0;
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;++i)
    {
    
        int color,price;
        scanf("%d%d",&color,&price);
        if(price<=p)
            now=i;
        if(now>=last[color])
            sum[color]=cnt[color];
        last[color]=i;
        ans+=sum[color];
        cnt[color]++;
    }
    printf("%d",ans);
    return 0;
}

2. Multiply the two numbers to get a complete square

For a sequence , Niuniu can multiply the number at any position in the sequence by any prime number every time .
Now he wants to know at least how many operations it takes to multiply the numbers at any two different positions in the sequence to be completely square .
Complete square ： about $x$, If it can be written in form $i\times i=x$, It is called a $x$ Complete square .
Tips ： The necessary and sufficient condition for a number to be a complete square number is that the exponents of all its prime factors are even .
Input description ：
Enter an integer in the first line N, Represents sequence length
On the next line, type N It's an integer , Represents the sequence
Output description ：
Output an integer for the answer

Example ：
Input
3
2 1 2
Output
1
explain
Just put the second 1 Multiply 2 that will do , So the sequence becomes 2 2 2, Multiplication of any two numbers is 4

analysis ：

Decomposing prime factor , Count whether the number of each factor in each number is odd or even . Only an even number of times, there is no need to operate ; There are odd times , Then it is necessary to judge whether there is the number of this factor , Take the smaller one to operate ; There are even odd times , Take the smaller one to operate .

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n, x, res;
map<int, int> p1, p2;

void divide(int n)
{
    
    for(int i=2;i<=n/i;i++)
        if(n%i==0)
        {
    
            int s=0;
            while(n%i==0)
            {
    
                n/=i;
                s++;
            }
            if(s % 2) p1[i] ++;
            else p2[i] ++;
        }
    if(n>1) p1[n] ++;
}

int main()
{
    
    cin >> n;
    for(int i = 0; i < n; i ++) 
    {
    
        cin >> x;
        divide(x);
    }
    for(int i = 0; i < 100002; i ++)
    {
    
        if(p1[i] != 0 && p1[i] < n) res += min(p1[i], n - p1[i]);
        else if(p1[i] != 0 && p2[i] != 0) res += min(p1[i], p2[i]);  
    }
    cout << res << endl;
    return 0;
}