1 Title: shopping list
Xiao Ming has just found a job. The boss is very nice, but the boss's wife loves shopping. When the boss is busy, he often asks Xiao Ming to help him go shopping in the mall. Xiao Ming is very bored, but it's hard to refuse. see, XX The big promotion is coming again! The boss's wife issued a long shopping list with discounts. Xiao Ming also has a quirk. As a last resort, he never swipes his card and gets it in cash. Now Xiao Ming is very upset. Please help him calculate how much cash he needs to withdraw from the ATM to finish this shopping. The ATM can only provide 100 yuan notes. Xiao Ming wants to withdraw as little cash as possible. It's enough. Your task is to calculate how much cash Xiao Ming needs to withdraw at least.
The following is a troublesome shopping list. In order to protect privacy, the item name is hidden.
****180.90% off
****10.25% off
****56.14 10% off
****10% off 104.65
****100.30% off
****297.15 half price
****26.75% off
****130.62 half price
****240.28 58% off
****20% off 270.62
****115.87% off
****247.34 95% off
****73.21% off
****101.00 half price
****79.54 half price
****278.44% off
****199.26 half price
****10% off 12.97
****76.30% off
****25.50% off
****84.98% off
****113.35% off
****166.57 half price
****20% off 42.56
****81.90% off
****131.78% off
****255.89 78% off
****10% off 109.17
****146.69% off
****139.33 65% off
****141.16% discount
****154.74% off
****59.42 20% off
****85.44% off
****293.70 88% off
****261.79 65% off
****11.30 88% off
****268.27 58% off
****128.29% off
****251.03 20% off
****208.39 75% off
****128.88 75% off
****10% off 62.06
****225.87 75% off
****12.89 75% off
****34.28 75% off
****62.16% off
****129.12 half price
****218.37 half price
****289.69 20% off
180.90 88
10.25 65
56.14 90
104.65 90
100.30 88
297.15 50
26.75 65
130.62 50
240.28 58
270.62 80
115.87 88
247.34 95
73.21 90
101.00 50
79.54 50
278.44 70
199.26 50
12.97 90
166.30 78
125.50 58
84.98 90
113.35 68
166.57 50
42.56 90
81.90 95
131.78 80
255.89 78
109.17 90
146.69 68
139.33 65
141.16 78
154.74 80
59.42 80
85.44 68
293.70 88
261.79 65
11.30 88
268.27 58
128.29 88
251.03 80
208.39 75
128.88 75
62.06 90
225.87 75
12.89 75
34.28 75
62.16 58
129.12 50
218.37 50
289.69 80
It should be noted that 88% discount refers to 88% of the bid price, while 80% discount refers to 80%, and so on.
In particular, the half price is calculated at 50%.
Please submit the amount that Xiao Ming wants to withdraw from the ATM. The unit is yuan.
The answer is an integer, similar to 4300. The end must be 00. Don't fill in any redundant content.
Special reminder: you are not allowed to bring calculators into the site or turn on your mobile phone.
Use the replacement and search built-in in the compiler to preprocess the data
Answer: 5200
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
double arr[100];
int discount[100];
int main()
{
int i=0;
double ans=0;
for(int i=0;i<50;i++)
{
scanf("%lf%d",&arr[i],&discount[i]);
ans+=arr[i]*discount[i]/100;
}
// while(scanf(cin>>arr[i]>>discount[i])
// {
// ans+=arr[i]*discount[i]/100;
// i++;
// }
cout<<ans<<endl;
return 0;
}
2 Title: arithmetic prime sequence
2, 3, 5, 7, 11, 13,... Are prime sequences.
Similar: 7,37,67,97127157 such an arithmetic sequence composed entirely of prime numbers is called arithmetic prime sequence.
The upper series has a tolerance of 30 and a length of 6.
In 2004, green worked with Chinese Tao Zhehuan to prove that there is a prime arithmetic sequence of arbitrary length.
This is an amazing achievement in the field of number theory!
Based on this theory, please search with confidence with the help of your computer:
What is the minimum tolerance value of an arithmetic prime sequence with a length of 10?
Note: what needs to be submitted is an integer. Do not fill in any redundant content and explanatory text.
Answer: 210
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
bool isprime(int x)
{
if(x==2||x==3)
return true;
else if(x%6!=1&&x%6!=5)
return false;
else
{
for(int i=5;i<sqrt(x);i+=6)
{
if(x%i==0||x%(i+2)==0)
return false;
}
return true;
}
}
int main()
{
for(int i=2;i<50000;i++)//Enumeration Prime Minister
{
if(isprime(i))
{
for(int d=5;d<10000;d++)//Enumeration tolerance
{
int ct=0,n=1;
while(isprime(i+d*n))
{
ct++;
n++;
}
if(ct==9)
{
cout<<i<<" "<<d<<endl;
}
}
}
}
return 0;
}
3 Title: Bearing Calculation
Title: Bearing Calculation
A batch of precious metal raw materials are neatly stacked in the high-tech laboratory of Planet X.
The shape and size of each metal raw material are exactly the same, but the weight is different.
Metal materials are strictly stacked into pyramids.
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
The number represents the weight of the metal block (larger unit of measurement).
The X on the bottom layer represents 30 extremely high-precision electronic scales.
Assuming that the weight of each raw material falls on the two metal blocks below very accurately,
Finally, the weight of all metal blocks is strictly and accurately distributed on the bottom electronic scale.
The unit of measurement of the electronic scale is very small, so the number displayed is very large.
The staff found that the indication of the electronic scale with the smallest reading was 2086458231
Please figure out: what is the indication of the electronic scale with the largest reading?
Note: what needs to be submitted is an integer. Do not fill in any redundant content.
Answer: 72665192664
When writing code, you will traverse the last row to find the minimum value. When the max and min functions are used for the maximum value, the card does not know why for a long time. The last output maximum value and minimum value are the minimum value.
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int n=29;
double arr[30][30];
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
scanf("%lf",&arr[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0)
arr[i][j]+=arr[i-1][j]/2;
else if(j==i)
arr[i][j]+=arr[i-1][j-1]/2;
else
arr[i][j]+=arr[i-1][j-1]/2+arr[i-1][j]/2;
}
}
double ans=arr[29][0],res=arr[29][0];
for(int i=0;i<30;i++)
{
ans=max(ans,arr[29][i]);
res=min(res,arr[29][i]);
// ans=max(arr[29][i,ans]);
// res=min(arr[29][i],res); Why are the two outputs with this minimum value???????
}
printf("%lf",2086458231/res*ans);
return 0;
}
4 Title: grid segmentation
6x6 square, cut into two parts along the edge of the grid.
The shape of these two parts is required to be exactly the same.
As shown in the figure: P1 png, p2. png, p3. PNG is a feasible segmentation method.
Trial calculation:
How many different segmentation methods are there, including these three segmentation methods.
Note: rotational symmetry belongs to the same segmentation method.
Please submit this integer and do not fill in any redundant content or explanatory text.
Idea: from the point in the upper left corner marked as (0, 0), it can be seen that the cut graphics are symmetrical about the point (3, 3). When one of the points (x,y) is 0 or 6, the cutting of the graphics is completed (note that when the point goes to (x,y), the point (6-x,6-y) should also be marked as gone due to the relationship of symmetry)
#include<stdio.h>
bool v[7][7];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int ans=0;
void dfs(int x,int y)
{
// v[x][y]=true;
// v[6-x][6-y]=true; It can't be written here. List x=2,y=3
// printf("x:%d y:%d\n",x,y);
if(x==6||x==0||y==6||y==0)
{
ans++;
return ;
}
for(int i=0;i<4;i++)
{
int n=x+dx[i],m=y+dy[i];
if(n>=0&&n<=6 && m>=0&&m<=6 &&v[n][m]==false )
{
v[n][m]=true;
v[6-n][6-m]=true;
dfs(n,m);
v[n][m]=false;
v[6-n][6-m]=false;
}
}
// v[x][y]=false;
// v[6-x][6-y]=false;
}
int main()
{
v[3][3]=true;
dfs(3,3);
printf("%d",ans/4);
return 0;
}
Title: 5 digits
There are many ways to find the k-th digit of an integer.
The following method is one.
//Find the digit length when x is expressed in decimal system
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
//Take the k-th digit of x
int f(int x, int k){
if(len(x)-k==0) return x%10;
return ____f(x/10,k)_________________; // Fill in the blanks
}
int main()
{
int x = 23574;
printf("%d\n", f(x,3));
return 0;
}
For the test data in the topic, 5 should be printed.
Please carefully analyze the source code and supplement the missing code in the underlined part.
Note: only submit the missing code, and do not fill in any existing content or explanatory text.
6 Title: maximum common substring
The maximum common substring length is:
Find the maximum length that can be matched in all substrings of two strings.
For example: "abcdkkk" and "baabcddabc",
The longest common substring that can be found is "abcd", so the maximum common substring length is 4.
The following program is solved by matrix method, which is a more effective solution for the case of small string size.
Please analyze the idea of this solution and complete the missing code in the underlined part.
Note: submit only the missing code, not the existing code and symbols. And don't submit explanatory text.
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = __________a[i-1][j-1]+1________________; //Fill in the blanks
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return 0;
}
7 Title: Date issue
Xiao Ming is sorting out a batch of historical documents. Many dates appear in these historical documents. Xiao Ming knows that these dates are from January 1, 1960 to December 31, 2059. What bothers Xiao Ming is that the formats of these dates are very different, including year / month / day, month / day / year and day / month / year. What's more troublesome is that the first two digits of the year are omitted, so that there are many possible dates corresponding to a date in the literature.
For example, 02 / 03 / 04 may be March 4, 2002, February 3, 2004 or March 2, 2004.
Given a date in the literature, can you help Xiao Ming judge which possible dates correspond to it?
input
A date in the format "AA/BB/CC". (0 <= A, B, C <= 9)
input
Output several different dates, one line for each date, in the format of "yyyy MM DD". Multiple dates are arranged from morning to night.
sample input
02/03/04
sample output
2002-03-04
2004-02-03
2004-03-02
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Idea: enumerate in turn. Remember to write code after reading the title. Sort it.
#include <stdio.h>
#include <string.h>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
struct date
{
int x,y,z;//Respectively represents month, year and day
};
bool cmp(date n,date m)
{
if(n.x!=m.x)
return n.x<m.x;
else
{
if(n.y!=m.y)
return n.y<m.y;
else
return n.z<m.z;
}
}
int main()
{
int a,b,c;
scanf("%d",&a);
getchar();
scanf("%d",&b);
getchar();
scanf("%d",&c);
vector<date> vi;
date kk;
//Date of judgment;
if( (b==1||b==3||b==5||b==7||b==8||b==10||b==12) &&c<=31&&c>0)
{
if(a>=60)
{
kk.x=a+1900;
}
else
{
kk.x=a+2000;
}
kk.y=b;
kk.z=c;
vi.push_back(kk);
}
else if( ((b==4||b==6||b==9||b==11)&&c<=30&&c>0 ) )
{
if(a>=60)
{
kk.x=a+1900;
}
else
{
kk.x=a+2000;
}
kk.y=b;
kk.z=c;
vi.push_back(kk);
}
else if( (b==2&&c<=28) || (b==2&&a%4==0&&c<=29) &&c>0 )
{
if(a>=60)
{
kk.x=a+1900;
}
else
{
kk.x=a+2000;
}
kk.y=b;
kk.z=c;
vi.push_back(kk);
}
//Month day year
if( (a==1||a==3||a==5||a==7||a==8||a==10||a==12) && b<=31 &&b>0 )
{
if(c>=60)
{
kk.x=c+1900;
}
else
{
kk.x=c+2000;
}
kk.y=a;
kk.z=b;
vi.push_back(kk);
}
else if( (a==4||a==6||a==9||a==11)&& b<=30&&b>0 )
{
if(c>=60)
{
kk.x=c+1900;
}
else
{
kk.x=c+2000;
}
kk.y=a;
kk.z=b;
vi.push_back(kk);
}
else if( a==2&&b<=28 || a==2&&b<=29&&c%4==0 &&b>0 )
{
if(c>=60)
{
kk.x=c+1900;
}
else
{
kk.x=c+2000;
}
kk.y=a;
kk.z=b;
vi.push_back(kk);
}
//Sun Moon year
if( (b==1||b==3||b==5||b==7||b==8||b==10||b==12) &&a<=31 &&a>0 )
{
if(c>=60)
{
kk.x=c+1900;
}
else
{
kk.x=c+2000;
}
kk.y=b;
kk.z=a;
vi.push_back(kk);
}
else if( (b==4||b==6||b==9||b==11)&&a<=30 &&a>0)
{
if(c>=60)
{
kk.x=c+1900;
}
else
{
kk.x=c+2000;
}
kk.y=b;
kk.z=a;
vi.push_back(kk);
}
else if( b==2&&a<=28&&a>0 || b==2&&a<=29&&c%4==0 &&a>0)
{
if(c>=60)
{
kk.x=c+1900;
}
else
{
kk.x=c+2000;
}
kk.y=b;
kk.z=a;
vi.push_back(kk);
}
sort(vi.begin(),vi.end(),cmp);
for(int i=0;i<vi.size();i++)
{
if(vi[i].x!=vi[i+1].x || vi[i].y!=vi[i+1].y || vi[i].z!=vi[i+1].z )//Prevent entering duplicate dates
printf("%d-%02d-%02d\n",vi[i].x,vi[i].y,vi[i].z);
}
return 0;
}
8 Title: make up the number of steamed stuffed buns
Xiao Ming eats breakfast at a steamed stuffed bun shop almost every morning. He found that this steamed stuffed bun shop has N kinds of steamers, of which the i steamer can just put Ai steamed stuffed buns. Each kind of steamer has many steamers, which can be regarded as infinite steamers.
Whenever a customer wants to buy X steamed stuffed buns, the uncle selling steamed stuffed buns will quickly select several cages of steamed stuffed buns, so that there are exactly X steamed stuffed buns in these cages. For example, there are three kinds of steamers, which can put 3, 4 and 5 steamed buns respectively.
When customers want to buy 11 steamed stuffed buns, uncle will choose 2 cages of 3 and 1 cage of 5 (or 1 cage of 3 and 2 cages of 4).
Of course, sometimes uncle baozi can't figure out the quantity customers want to buy anyway. For example, there are three kinds of steamers, which can put 4, 5 and 6 steamed buns respectively. When customers want to buy seven steamed stuffed buns, uncle can't come up with it.
Xiao Ming wants to know how many kinds of numbers are there that uncle baozi can't figure out.
input
The first line contains an integer n. (1 <= N <= 100)
Each of the following N lines contains an integer AI. (1 <= Ai <= 100)
output
An integer represents the answer. If there are infinite numbers that cannot be summed up, output INF.
For example,
Input:
2
4
5
The program should output:
6
Another example is,
Input:
2
4
6
The program should output:
INF
Example explanation:
For example 1, the numbers that cannot be rounded up include: 1, 2, 3, 6, 7 and 11.
For example 2, none of the odd numbers can be summed up, so there are infinite numbers.
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Idea: see the code for details of dynamic planning
#include<stdio.h>
#include<algorithm>
using namespace std;
bool dp[10000];//Default = = false for external application, because 1 < = AI < = 100, and only 99 and 100 in the worst case,
//We only need to find the number that can be made up continuously, and the number of each is larger than the minimum number of steamed stuffed buns
int main()
{
int arr[110];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
sort(arr,arr+n);
dp[0]=true;
bool k=false;
int ss;
for(int i=0;i<n;i++)
{
int ct=0;//Record the number of consecutive steamed stuffed buns
for(int j=0;j<10000;j++)
{
if(dp[j]==true)
{
dp[j+arr[i]]=true;
if(dp[j-1]==true)
ct++;
else
ct=0;
}
if(ct>=arr[0])//Here we find j. the following numbers can be summed up, but the loop
//It's not over. We need to enumerate the number of other steamed stuffed bun cages to see if we can cut some numbers, such as 6, 7 and 8
{
ss=j;//It is used to record the number after ss, which can be summed up
k=true;
break;
}
}
}
int ans=0;//count
if(k==false)
printf("INF");
else
{
for(int i=1;i<ss;i++)
{
if(dp[i]==false)
ans++;
}
printf("%d",ans);
}
return 0;
}
9 Title: Chocolate
On children's Day K A child came to Xiaoming's house as a guest. Xiao Ming took out his precious chocolate to entertain the children. Xiao Ming has N Chocolate, of which i Block is Hi x Wi A rectangle consisting of squares. To be fair, Xiao Ming needs to start from here N Cut out of a piece of chocolate K Give the children a piece of chocolate. The cut chocolate needs to meet: 1. The shape of a square is an integer 2. Same size
For example, a piece of 6x5 chocolate can cut 6 pieces of 2x2 chocolate or 2 pieces of 3x3 chocolate.
Of course, children all want to get as much chocolate as possible. Can you help little Hi calculate the maximum side length?
input
The first line contains two integers n and K. (1 <= N, K <= 100000)
Each of the following N lines contains two integers hi and wi. (1 <= Hi, Wi <= 100000)
Input to ensure that each child can get at least one 1x1 chocolate.
output
Output the maximum possible side length of the cut square chocolate.
Sample input:
2 10
6 5
5 6
Sample output:
2
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Idea: dichotomy, l indicates left pointer, R indicates pointer, M = (L+R) / 2;
The title shows that l = 1 and R = max (maximum side length) are constantly reducing the values of L and r.
#include<stdio.h>
#include<algorithm>
using namespace std;
struct xx
{
int x,y;//Defines a rectangle that represents length and width
}arr[100007];
int main()
{
int n,k,maxn=-1;//maxn maximum side length
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d%d",&arr[i].x,&arr[i].y);
maxn=max(maxn,max(arr[i].x,arr[i].y)) ;
}
int m, l=1,r=maxn;//dichotomy
while(l<r&&r-l!=1)
{
m=(l+r)/2;
long long res=0;//Count the number of chocolates when the side length is m
for(int i=0;i<n;i++)
{
res+=(arr[i].x/m)*(arr[i].y/m);
}
if(res<k)//The selected side length is too long
r=m;
else//The side length is small
l=m;
}
// Anyway, after the above processing, the result is one of the two
long long res=0;
for(int i=0;i<n;i++)
{
res+=(arr[i].x/r)*(arr[i].y/r);
}
if(k<res)
printf("%d",r);
else
printf("%d",l);
return 0;
}
10 Title: k-fold interval
Given a sequence with length N, A1, A2,... AN, if the sum of a continuous subsequence Ai, Ai+1,... AJ (I < = J) is a multiple of K, we call this interval [i, j] a k-fold interval.
Can you find out how many K-times intervals there are in the sequence?
input
The first line contains two integers n and K. (1 <= N, K <= 100000)
Each of the following N lines contains an integer AI. (1 <= Ai <= 100000)
output
Output an integer representing the number of K-times intervals.
For example,
Input:
5 2
1
2
3
4
5
The program should output:
6
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 2000ms
Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Thinking, prefix and, I wrote a code of O(N Λ 2) when n=100000. I went to have a look Big guy's idea O(N), and then wrote one by yourself (you can go to see the boss's idea, which is very clear).
O(N∧2)
#include<stdio.h>
int arr[100005];
long long sum[100005];//Sum of the first i digits
int main()
{
int n,k;
long long ans=0;//ans count
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
sum[i]=arr[i]+sum[i-1];
if(sum[i]%k==0)//Here, the sum of numbers from 1 to i is a multiple of K.
ans++;
}
for(int i=1;i<n;i++)//Enumerating sum arrays
{
for(int j=1;j<n;j++)//Enumeration distance
{
if((sum[j+i]-sum[i])%k==0&&i+j<=n)//Prevent array index overflow
{
ans++;
}
}
}
printf("%d",ans);
return 0;
}
O (n), prefix and remainder.
#include<stdio.h>
int arr[100005];
long long sum[100005];//The first i digits modulus K
long long res[100005];//It is used to count how many numbers take the same modulus. You can only use long long, otherwise when N=100000, you can't pass the data
int main()
{
int n,k;
long long ans=0;//ans count
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
sum[i]=(arr[i]+sum[i-1])%k;
res[sum[i]]++;
}
for(int i=0;i<k;i++)
{
ans+=res[i]*(res[i]-1)/2;
}
printf("%lld",ans+res[0]);
return 0;
}
Big guy's code:
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int sum[N],a[N],res[N];
int n,k;
ll ans=0;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=(sum[i-1]+a[i])%k;//Prefix and modulus
ans+=res[sum[i]];//Update answer
res[sum[i]]++;//Two equal prefixes and can form a k-fold interval
}
cout<<ans+res[0]<<endl;
return 0;
}