美文网首页
「数学知识」练习

「数学知识」练习

作者: 云中翻月 | 来源:发表于2019-03-20 22:10 被阅读0次
0x3B「数学知识」练习

POJ2480 Longge's problem
要求\sum_{i=1}^{n}gcd(i,n)。
考虑满足gcd(x,n)=1的x的数目就是\varphi(n)，那么满足gcd(x,n)=p的x的个数就是满足gcd(x/p,n/p)=p/p=1的x/p的个数，就是\varphi(n/p)。
因此，为了使n/p为整数，我们考虑对于n的每个约数p，它对答案的贡献就是p*(1~n中满足gcd(x,n)=p的x的个数)。也就是说每个约数p的贡献就是p*\varphi(n/p)。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
满足gcd(x, n) = 1 的个数是欧拉函数φ(n)，那么可以知道，满足gcd(x, n) = p 的个数可以这么求：
x 和 n 同时除以 p ，那么gcd(x/p, n/p) = 1 ，那么个数就是φ(n/p)
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=65536+5;
const int INF=0x3f3f3f3f;
int n;
int phi(int x){
    int ans=x;
    int m=(int)sqrt(x+0.5);
    for(int i=2;i<=m;i++){
        if(x%i==0){
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("Longge's problem.in","r",stdin);
//  cout<<phi(12)<<endl;
    while(cin>>n){
        ll ans=0;
        int m=(int)sqrt(n+0.5);
        for(int i=1;i<=m;i++){
            if(n%i==0){
                ans+=(ll)phi(n/i)*i;
                if(n/i!=i) ans+=(ll)phi(i)*(n/i);
            }
//          if(n/i!=i) ans+=(ll)phi(i)*(n/i); 注意这句话不是放在这里啊 
        }
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1061 青蛙的约会
显然，题目要求满足条件x+mt\equiv y+nt(mod \;l)的最小非负整数t。若t不存在，则输出“Impossible”。
将上式变形得(m-n)t\equiv y-x(mod \;l)
设(m-n)t=-Yl+y-x，即倍数为-Y
移项得(m-n)t+Yl=y-x
根据贝祖定理，若gcd(m-n,l)|y-x，则存在t满足条件。
跑一边exgcd就是答案（通过exgcd跑出的x乘以(y-x)/gcd(m-n,l)和对(l/gcd(m-n,l))取模，将答案调整到满足条件的最小非负值），注意讨论m-n的符号。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
ll _x,_y,n,m,l,x,y,a,b;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,(a+b)%b,x,y); //第二个参数不要写成a%b 否则d可能为负数 
    ll z=x;
    x=y,y=z-y*(a/b);
    return d; 
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("青蛙的约会.in","r",stdin);
    cin>>_x>>_y>>m>>n>>l;
    if(_y<_x){
        swap(_x,_y),swap(n,m);
    }
    int d;
    if((_y-_x)%(d=exgcd(m-n,l,x,y))==0){
        x*=(_y-_x)/d;
        while(x<0){
            x+=l/d;
        }
        cout<<x%(l/d);
    }
    else{
        cout<<"Impossible";
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

3B04 Xiao 9*大战朱最学
中国剩余定理模板题，不再赘述
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10+5;
const int INF=0x3f3f3f3f;
ll M=1,m[maxn],a1[maxn],n,a,b,x,y,ans=0;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,(a+b)%b,x,y);
    ll z=x;
    x=y,y=z-(a/b)*y;
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("大战朱最学.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>m[i]>>a1[i],M*=m[i];
    for(int i=1;i<=n;i++){
        int t=exgcd(M/m[i],m[i],x,y);
        x=((x%m[i])+m[i])%m[i];
        ans=(ans+M/m[i]*a1[i]*x)%M;
    } 
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ2947 Widget Factory
线性同余方程组，要求所有解都在[3,9]内，且为整数。
先不管同余问题，跑一边高斯消元。
由于方程数和变量数不一定相等，所以用两个变量i和j，记录当前处理过的方程数和处理过的变量数。
跑完高斯消元后，如果此时后面没有处理过的方程中出现常数矩阵非零的情况，就意味着出现了矛盾，即无解。
如果不是无解，而且没有处理完所有变量，方程就已经全部处理完了，或者处理的有效方程数和变量数不同，就是出现了自由元，即存在多组可行解的情况。
最后考虑构造一组[3,9]内的解：由于此时系数矩阵已经是对角矩阵，所以我们可以逆序枚举所有变量和所有方程，依次尝试[3,9]之间的所有数字，判断这个变量能否取这个值，若能，就让它取这个值即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int INF=0x3f3f3f3f;
int n,m,i,j,l,k,c[maxn][maxn],a[maxn],b[maxn],num,x;
char s1[10],s2[10];
int cal(char s[]) {
    if(s[0]=='M') return 1;
    if(s[0]=='T'&&s[1]=='U') return 2;
    if(s[0]=='W') return 3;
    if(s[0]=='T'&&s[1]=='H') return 4;
    if(s[0]=='F') return 5;
    if(s[0]=='S'&&s[1]=='A') return 6;
    if(s[0]=='S'&&s[1]=='U') return 7;
}
void solve() {
    i=j=1;
    while(i<=m&&j<=n) { //m个方程 每个方程最多n个未知数
        for(l=i; l<=m; l++) if(c[l][j]) break; //找到含有第j个变元的方程
        if(l>m) {
            j++;
            continue;
        }
        int x=c[l][j];
        for(k=j; k<=n; k++) {
            swap(c[i][k],c[l][k]);
        }
        swap(b[i],b[l]);//将含有第j个变元的方程从第l行换到第i行 
        for(k=i+1; k<=m; k++) { //用第i行的方程 去消去后面所有方程中的第j个变元 
            int y=c[k][j];
            for(l=j; l<=n; l++) {
                c[k][l]=((c[k][l]*x-c[i][l]*y)%7+7)%7;
            }
            b[k]=((b[k]*x-b[i]*y)%7+7)%7;
        }
        i++,j++;
    }
    for(k=i; k<=m; k++)
        if(b[k]) {
            cout<<"Inconsistent data."<<endl;
            return;
        }
    if(i!=j||j<=n) {
        cout<<"Multiple solutions."<<endl;
        return;
    }
    for(i--,j--;i;i--,j--){ //这时的c矩阵为对角矩阵 
        for(l=0,k=j+1;k<=n;k++) l+=c[i][k]*a[k];
        for(k=3;k<=9;k++){
            if(((c[i][j]*k)%7+7)%7==((b[i]-l)%7+7)%7) a[j]=k;
        }
    }
    for(i=1; i<n; i++) cout<<a[i]<<" ";
    cout<<a[n]<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Widget Factory.in","r",stdin);
    while(cin>>n>>m) {
        if(n==0&&m==0) break;
        memset(c,0,sizeof(c));
        for(i=1; i<=m; i++) {
            cin>>num>>s1>>s2;
            b[i]=cal(s2)-cal(s1)+1;
            for(j=1; j<=num; j++) {
                cin>>x;
                c[i][x]++;
            }
            for(j=1; j<=n; j++) {
                c[i][j]=(c[i][j]%7+7)%7;
            }
        }
        solve();
    }
    return 0;
}
#endif

3B13 守卫者的挑战
期望dp，根据题目提示，可以做出类似背包的状态定义。
状态定义：f[i,j,k]表示前i项挑战，成功了j项，背包剩余容量为k的概率（用坐标平移解决k为负数情况）。
状态转移：分第i项挑战成功和挑战失败分别讨论。
PS：代码中有一处注释的写法是错的，目前原因未知。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
http://www.pianshen.com/article/362730004/
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int base=200;
const int INF=0x3f3f3f3f;
double p[maxn],f[maxn][maxn][maxn*2],ans=0.0;
int a[maxn],n,l,K;
int main() {
//  ios::sync_with_stdio(false);
    //freopen("守卫者的挑战.in","r",stdin);
    cin>>n>>l>>K;
    if(K>n) K=n;
    for(int i=1;i<=n;i++) cin>>p[i],p[i]/=100.0;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[0][0][K+base]=1.0;//f[i,j,k]表示前i项挑战 成功了j项 背包剩余容量为k的概率 
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            for(int k=-n;k<=n;k++){
                f[i][j][k+base]+=f[i-1][j][k+base]*(1-p[i]); //失败 
                if(j+1<=i) f[i][j+1][min(k+a[i],n)+base]+=f[i-1][j][k+base]*p[i];//成功 
//              if(j+1<=i) f[i][j][k+base]+=f[i-1][j-1][k-a[i]+base]*p[i];//这样写不行 原因未知 
            } 
        }
    }
    for(int i=l;i<=n;i++){
        for(int j=0;j<=n;j++){
            ans+=f[n][i][j+base];
        }
    }
    printf("%.6lf",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

3B14 换教室
NOIP的题目，floyd+期望dp。
细节挺多，但逻辑不难，仔细思考即可。
状态定义：f[i,j,k]表示前i个时间段申请了j个教室 k=0:i不换 k=1:i换的最小体力期望。
状态转移：分四类情况：j为申请的次数
1 i和i-1都没有申请 j>=0
2 i没有申请 i-1申请 j>=1
a i-1申请成功 妞妞从d[i-1]走到c[i]
b i-1申请失败 妞妞从c[i-1]走到c[i]
3 i申请 i-1没有申请 j>=1
a i申请失败 妞妞从c[i-1]走到c[i]
b i申请成功 妞妞从c[i-1]走到d[i]
4 i和i-1都申请 j>=2
a i-1申请失败 i申请失败 妞妞从c[i-1]走到c[i]
b i-1申请成功 i申请成功 妞妞从d[i-1]走到d[i]
c i-1申请失败 i申请成功 妞妞从c[i-1]走到d[i]
d i-1申请成功 i申请失败 妞妞从d[i-1]走到c[i]
注意：这道题计算的是期望，所以所有状态应该是加起来 而不是取min。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int maxv=300+5;
const int INF=0x3f3f3f3f;
int n,m,v,e,c[maxn],d[maxn];
double f[maxn][maxn][2],p[maxn],G[maxv][maxv];
int main() {
//  ios::sync_with_stdio(false);
    //freopen("换教室.in","r",stdin);
    cin>>n>>m>>v>>e;
    for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) f[i][j][0]=f[i][j][1]=10000000.0;
    for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) G[i][j]=G[j][i]=10000000.0;
    for(int i=1;i<=v;i++) G[i][i]=0.0;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++)cin>>d[i];
    for(int i=1;i<=n;i++)cin>>p[i];
    p[0]=1.0;//这句话可有可无  
    int x,y;
    double w;
    for(int i=1;i<=e;i++)cin>>x>>y>>w,G[x][y]=min(G[x][y],w),G[y][x]=G[x][y];
    for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
    f[0][0][0]=0.0;
    //f[i][j][0]表示前i节课，申请j节课，第i节课没有申请的最小期望 
    //f[i][j][1]表示前i节课，申请j节课，第i节课申请的最小期望 
//  cout<<G[1][2]<<G[1][3]<<G[2][3]<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            double &ans1=f[i][j][0],&ans2=f[i][j][1];
            ans1=min(ans1,f[i-1][j][0]+G[c[i-1]][c[i]]); //第i-1节课没有申请 
            if(j)ans1=min(ans1,(f[i-1][j][1]+G[c[i-1]][c[i]])*(1.0-p[i-1])+(f[i-1][j][1]+G[d[i-1]][c[i]])*p[i-1]); //第i-1节课申请 申请失败+申请成功
            if(j)ans2=min(ans2,(f[i-1][j-1][0]+G[c[i-1]][c[i]])*(1.0-p[i])+(f[i-1][j-1][0]+G[c[i-1]][d[i]])*p[i]); //第i-1节课没有申请 第i节课申请失败+申请成功 
            if(j>=2)ans2=min(ans2,(f[i-1][j-1][1]+G[c[i-1]][c[i]])*(1.0-p[i-1])*(1.0-p[i])+(f[i-1][j-1][1]+G[d[i-1]][d[i]])*p[i-1]*p[i]+(f[i-1][j-1][1]+G[c[i-1]][d[i]])*(1.0-p[i-1])*p[i]+(f[i-1][j-1][1]+G[d[i-1]][c[i]])*p[i-1]*(1.0-p[i])); //第i-1节课申请 都失败+都成功+一个成功一个失败 
        }
    }
    double ans=10000000.0;
    for(int i=0;i<=m;i++) ans=min(ans,f[n][i][0]),ans=min(ans,f[n][i][1]);
    printf("%.2lf",ans); 
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

3B16 魔法珠
首先每一堆魔法珠都相互独立且是一个公平组合游戏，所以将每一堆魔法珠视为一个有向图游戏，dfs求其SG函数，用f[x]记忆化搜索，用一个全局变量num和v数组记录当前层面的SG函数，最后用一个空循环作为mex计算即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxa=1000+5;
const int INF=0x3f3f3f3f;
int f[maxa],num=0,ans,temp,v[maxa],n;
int SG(int x){
    if(f[x]!=-1) return f[x];//记忆化搜索 
    int now=++num,p=0;
    for(int i=1;i*i<=x;i++){ //枚举所有约数 即枚举所有有向图游戏的后继状态 包括1但不包括x 
        if(x%i==0){
            if(i<x) p^=SG(i);
            if(i*i!=x&&i>1&&i<x) p^=SG(x/i);
        }
    }
    for(int i=1;i*i<=x;i++){ //枚举删去哪一堆 
        if(x%i==0){
            if(i<x) v[p^f[i]]=now;
            if(i*i!=x&&i>1&&i<x) v[p^f[x/i]]=now;
        }
    }
    int pos=0;
    for(;v[pos]==now;pos++);//mex操作 
    return f[x]=pos;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("魔法珠.in","r",stdin);
    while(cin>>n){
        memset(f,-1,sizeof(f)),ans=0;
        for(int i=1;i<=n;i++) cin>>temp,ans^=SG(temp);
        if(ans) cout<<"freda"<<endl;
        else cout<<"rainbow"<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1704 Georgia and Bob
将棋子两两结对考虑，将两个棋子之间的空格作为nim博弈中一堆石子的个数，全部异或起来就是答案。
解释为什么这么做：最终局面显然是n个棋子位于1,2,3...n的位置，这时每对棋子间距为0（事实上，当一人面对所有棋子中每对棋子间距为0时，他已经处于必输局面）。
对于移动棋子的操作，可以等效于以下情况

图片.png
移动每对棋子中右边的棋子，相当于从石子堆中取走石子。
图片.png
移动每对棋子中左边的棋子，虽然相当于从石子堆中增添石子，但是另一个人都可以对右边的棋子用同样的操作回到原来的个数。
PS：当棋子为奇数的时候，增添一个棋子，位于位置0即可。
图片.png
代码如下 
/*

*/
#define method_1
#ifdef method_1
/*
挑战p324 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int a[maxn],n,t;
int main() {
    ios::sync_with_stdio(false);
    //freopen("Georgia and Bob.in","r",stdin);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n&1) a[++n]=0;
        sort(a+1,a+n+1);
        int ans=0;
        for(int i=1;i<n;i+=2) ans^=(a[i+1]-a[i]-1);
        if(ans) cout<<"Georgia will win"<<endl;
        else cout<<"Bob will win"<<endl;
    } 
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

相关文章

  • 「数学知识」练习

    0x3B「数学知识」练习 POJ2480 Longge's problem要求。考虑满足gcd(x,n)=1的x的...

  • 《整理与复习》教学反思1

    本课通过复习让学生经过系统整理和复习所学数学知识的过程，并在这个过程中进一步感受不同数学知识之间的内在练习和相似内...

  • 《整理与复习》教学反思2

    本课通过复习让学生经过系统整理和复习所学数学知识的过程，并在这个过程中进一步感受不同数学知识之间的内在练习和相似内...

  • 设计课堂练习的策略

    练习设计串成串 数学练习的设计要突出数学知识之间的联系。吴老师的课堂中经常出现的步步为营的练习串，体现了层...

  • 2019-03-01

    《数学知识点》思维导图练习 2019年3月1日，今天是思维导图学习线上第8次学习及练习作业的提交。提到数学，哈哈，...

  • 练习设计串成串

    数学练习的设计要突出数学知识之间的联系。教师在课堂中要经常设计步步为营的练习串，体现层次性和发展性。在解决问题的过...

  • 2020-04-22形线画不只是形和线

    形线画，是习字运笔的练习；是几何空间思维的启蒙，是数学知识的应用；是个体与集体和谐相处的社交启蒙，更是内在成...

  • 数学排位赛-2021-02-16

    数学知识，老师课堂讲授是主要的形式；去培训班学数学知识，家长给孩子讲解数学知识，偶尔几次可以，经常做就得不偿失了。...

  • 生活中的数学

    一、数学知识在人们生活中的应用 生活中的数学知识最基本应用是在人们的衣、食、 住、行等四个方面。 (一)数学知识在...

  • 浅谈因式分解中的数学思想

    中学数学内容(基本要求)的整体结构有两根强有力的支柱，即数学知识与数学思想方法。数学思想方法产生数学知识，数学知识...

网友评论

      本文标题：「数学知识」练习

      本文链接：https://www.haomeiwen.com/subject/eohxvqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|「数学知识」练习|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！