18图灵班编程作业一

Task1

Code

#include <cstdio>
int count(int n){
    int sum=0;
    for(int i=1;i<=n-1;i++){
        sum+=i;
    }
    printf("%d\n",sum%n);
}
int main(){
    for(int i=1;i<=10000;i++){
        count(i);
    }
    return 0;
}

Conclusion

$$f(n)=\left\{ \begin{aligned} & 0&\text{if $n$ is odd} \\ & \frac n2 &\text{if $n$ is even} \\ \end{aligned} \right.$$

Proof

No matter n is odd or even ,we could get that

$$f(n)=1+2+\ldots+n-1=\frac{n^2-n}{2}=\frac{n(n-1)}{2}=kn$$
We could make f(n)=kn,whether k is integer depends on $$k=\frac{n-1}{2}$$
When n is odd,n-1 is even,then k is integer,so the result is zero.
When n is even,n-2 is even,and $$k=\frac{n-2}{2}+\frac{1}{2}$$
$$f(n)=(\frac{n-2}{2})n+\frac{1}{2}n$$
Since n-2 is even,f(n) mod n equal $$\frac{1}{2}n$$

Task2

Code

#include <cstdio>
#include <cmath>
long long count(int i,int n){
    long long sum=0;
    for(int t=1;t<=n-1;t++){
        sum+=pow(t,i);
        sum%=n;
    }
    return sum;
}
int main(){
    for(int n=2;n<=15;n++){
        for(int i=2;i<=n-1;i++){
            printf("%4d ",count(i,n));
        }
        printf("\n");
    }
    return 0;
}

Conclusion

Here is the output
Because the result of pow() is too large,n couldn't over 15.

   2
   2    0
   0    0    4
   1    3    1    3
   0    0    0    0    6
   4    0    4    0    4    0
   6    0    6    0    6    0    6
   5    5    3    5    5    5    3    5
   0    0    0    0    0    0    0    0   10
   2    0    2    0    2    0    2    0    2    0
   0    0    0    0    0    0    0    0    0    0   12
   7    7    7    7    5    7    7    7    7    7    5    7
  10    0    7    0   10    0    7    0   10    0    7    0    9

It is not finished,emm....give me more time...,