精华内容
下载资源
问答
  • 数论之模加法运算

    千次阅读 2017-04-12 21:16:10
    问题一个mm位的整数,有多少可以...数论中的模加法运算有这样的性质(对乘法也是一样):(a+b) mod n===(a mod n+b mod n) mod n(a mod n+b) mod n(a+b mod n) mod n \begin{array}{lcl} (a+b)\ \text

    问题

    一个m位的整数,有多少可以被整数n整除?其中m可以大于15。

    • 测试输入
      1 3
    • 测试输出
      4

    分析1

    这个问题显然不能穷举所有的情况。数论中的模加法运算有这样的性质(对乘法也是一样):

    (a+b) mod n===(a mod n+b mod n) mod n(a mod n+b) mod n(a+b mod n) mod n

    由此可见,一个数的取模问题可以拆分成两个求和数的取模问题,这显然属于动态规划能够解决的问题。对于一个m位的整数x,可以将其按照十进制拆解为x=x0×10m1+x1×10m2++xm2×10+xm1。对于其中的i1i位做如下分析:
    j=xi1 mod n,则

    (xi1×10+xi) mod n====[(xi1×10) mod n+xi] mod n{[(xi1 mod n)×10] mod n+xi} mod n[(j×10) mod n+xi] mod n(j×10+xi) mod n

    由此定义c[i,j]为前i位数模n余数为j的个数,原问题为c[m,0]。第i位的取值k=09,穷举一遍后前i位余数为(j10+k)%n的个数,等于前i1位余数为j的个数的累计和。从而递归式为

    {c[0,0]=1,c[i,j]=0,c[i,(j10+k)%n] +=c[i1,j],i=0,j0i0,k=09

    代码1

    import java.util.Scanner;
    
    public class ModNums {
        static void solution(long[][] c, int m, int n) {
            for (int i = 0; i < n; i++) {
                c[0][i] = 0L;
            }
            c[0][0] = 1L;
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < 10; k++) {
                        c[i][(j * 10 + k) % n] += c[i - 1][j];
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int m = sc.nextInt();
            int n = sc.nextInt();
            long[][] c = new long[m + 1][n];
            solution(c, m, n);
            System.out.println(c[m][0]);
        }
    }

    变形

    一个m位的整数,其中有某些位不确定,用”X”表示,有多少可以被整数n整除?

    • 测试输入
      999999999X 3
    • 测试输出
      4

    分析2

    整体和原问题一样,只是不确定的位才需要穷举一遍,确定的位直接更新即可。

    代码2

    import java.util.Scanner;
    
    public class AmbiguousNums {
        static void solution(long[][] c, String seq, int n) {
            int length = seq.length();
            for (int i = 0; i < n; i++) {
                c[0][i] = 0L;
            }
            c[0][0] = 1L;
            for (int i = 1; i <= length; i++) {
                char ch = seq.charAt(i - 1);
                for (int j = 0; j < n; j++) {
                    if (ch == 'X') {
                        for (int k = 0; k < 10; k++) {
                            c[i][(j * 10 + k) % n] += c[i - 1][j];
                        }
                    } else {
                        int k = ch - '0';
                        c[i][(j * 10 + k) % n] += c[i - 1][j];
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String seq = sc.next();
            int length = seq.length();
            int n = sc.nextInt();
            long[][] c = new long[length + 1][n];
            solution(c, seq, n);
            System.out.println(c[length][0]);
        }
    }
    展开全文
  • 模n加法——元素阶的终极规律

    千次阅读 2020-03-11 10:48:22
    Z6={0,1,2,3,4,5}, 6 加法的构成的群中,群的阶=?...取其中的元素1,不停地对自身进行6加法,即对本身进行幂运算。 可得: 5=5 5+5=10 5+5+5=15 5+5+5+5=20 5+5+5+5+5=25 5+5+5+5+5+5=30 故...

    Z6={0,1,2,3,4,5},模 6 加法的构成的群中,群的阶=?, 元素 5 的阶 |5 |=? 。

    我们知道,群的阶等于元素个数6,
    我们看<Z6,+>中的元素{0,1,2,3,4,5}。取其中的元素1,不停地对自身进行模6加法,即对本身进行幂运算。
    可得:
    5=5
    5+5=10
    5+5+5=15
    5+5+5+5=20
    5+5+5+5+5=25
    5+5+5+5+5+5=30
    故|5|=6
    考虑大数字不好计算,让我们通过编程找规律。

    /*
    模n加法,群的阶=n,元素的阶=最少几次方(几次相加)=本身。
    下面来求元素的阶
    */
    
    #include<iostream>
    #include<iomanip>
    using namespace std;
    int as(int a)
    {
    	int i, j = 0;
    	for (i = 2; i < a; i++)
    		if (a % i == 0)
    		{
    			j = 1; break;
    		}
    	return j;
    }
    int main()
    {
    	int x, y, i;
    	int a = 15, b = 4;//a为元素个数和模a加法中的a.b为预留空间
    	for (i = 0; i < a; i++)
    		cout << setw(b) << i;
    	for (y = 2; y <= a; y++)
    		//	if(as(y))
    	{
    		cout << endl << setw(b) << y;
    		for (x = 1; x < y; x++)
    			for (i = 2; i < y + 2; i++)
    				if ((i * x) % y == x)
    				{
    					cout << setw(b) << i-1; break;
    				}
    	}
    	return 0;
    }
    

    最上方
    运行结果最上方一行为元素,最左方一列为元素个数,其它均为元素的阶。
    不难看出:元素的阶=n/(n与元素的最大公约数)
    |5|=6/(6与5最大公约数=1)=6

    展开全文
  • [ 补码、反码、原码的基本概念(先接受,再理解)]这个先不写~~ 下面以C语言说明补码的运算 int main() { char a; a=127; a+=1;... //声明变量只是开辟了... //但是负零的补码解释为负的值,即-2^n只有补码,只...
    1. [ 补码、反码、原码的基本概念(先接受,再理解)]这个先不写~~
    2. 下面以C语言说明补码的运算
    int  main()
    {
    	char a;
    	a=127;
    	a+=1;
    	a+=1;
    	//声明变量只是开辟了内存空间,赋值或运算赋值使得其值变化,
    	//参加运算的都是补码,展现在调试器和显示器上的是真值,即展示之前先要将补码还原成原码
    	//但是负零的补码解释为负的模值,即-2^n只有补码,只在赋值和运算赋值中出现,当然能在显示屏上出现
    }
    
    

    signed char型占用8位(也就是一个字节),我们知道,8位有符号型能够表示的补码范围是-128~+127,问题来了,1000 0000 表示的是-0吗?就是你想的那样,它表示-128;
    用补码表示0时,本来有两种形式的:1000 0000 和 0000 0000,但是为了增加可表示范围,规定-128的补码是1000 0000,-128没有原码,也没有反码;
    现在看上面那段代码,第一次加1后,a的值变为-128,具体过程是这样的:赋值和运算并赋值过程中都是以补码形式进行的,输出或者展示到显示器(比如debugger watches)之前先求出其原码,再呈现。第一次加一后,结果用补码表示是:1000 000,这时a是-128;再次加一,结果用补码表示是:1000 0001,这时a是-127.

    展开全文
  • 今天用django模板显示数据的时候,想根据数据库内id号取模来实现显示不同的...功夫不负苦心人,在用了N多个关键词google了之后。终于找到一条能实现基本功能的替代方法就是: 用django的divisibleby标签实现,如下:

    今天用django模板显示数据的时候,想根据数据库内id号取模来实现显示不同的CSS类。结果测试了一天也没运算成功。后来查了大量官方文档才知道,模板是不支持数学运算的(真是个让人绝望的缺陷)。没办法,网站还是要做下去的。只能想想别的办法。

    功夫不负苦心人,在用了N多个关键词google了之后。终于找到一条能实现基本功能的替代方法就是:

    用django的divisibleby标签实现,如下:

    {% for each in somelist %}

    {% if forloop.counter0|divisibleby:2 %}

    <div class=”class1″></div>

    {% else %}

    <div class=”class2″></div>

    {% endif %}

    {% endfor %}

    divisibleby标签的意义是用后面的参数去除,除尽为True,否则为False


    感觉很赞的一个设计,django的模板里面是用一个tags可以实现,加法,减法,乘法,除法的运算。嘿嘿

    先看一下django 官方的解释

     For creating bar charts and such, this tag calculates the ratio of a given
        value to a maximum value, and then applies that ratio to a constant.
        For example::
            <img src='bar.gif' height='10' width='{% widthratio this_value max_value 100 %}' />
        Above, if ``this_value`` is 175 and ``max_value`` is 200, the image in
        the above example will be 88 pixels wide (because 175/200 = .875;
        .875 * 100 = 87.5 which is rounded up to 88).

    这说明,widthratio 通常用来显示图表,比例时用的,一个数字占了多少百分比等。但仔细想想,如果将某些数字变成特定的数字,不就是乘除法运算了吗?请看:

    乘法 A*B: {% widthratio A 1 B %}
    除法 A/B: {% widthratio A B 1 %}
    
    利用 add 这个filter ,可以做更疯狂的事:
    
    计算 A^2: {% widthratio A 1 A %}
    计算 (A+B)^2: {% widthratio A|add:B 1 A|add:B %}
    计算 (A+B) * (C+D): {% widthratio A|add:B 1 C|add:D %}

    当然,这种方法在django中实现乘除法比较变态,看起来也不爽,更好的方法,是可以扩展自己的标签。在后面打算自己扩展一个计算乘法的标签,应该好很多。
    在django中实现其它一些简单的计算,参考这篇文章:http://www.yihaomen.com/article/python/186.htm
    用django template tag 的方式实现可以参考这篇文章:
    http://www.yihaomen.com/article/python/339.htm


    Django模版加法:

    {{ value|add:10}}
    value=5,则返回15 Django模版减法:
    {{value|add:-10}}
    value=5,则返回-5,这个比较好理解,减法就是加一个负数 Django模版乘法:
    {%  widthratio 5 1 100 %}
    上面的代码表示:5/1 *100,返回500,widthratio需要三个参数,它会使用 参数1/参数2*参数3,所以要进行乘法的话,就将参数2=1即可 Django模版除法
    {%  widthratio 5 100 1 %}
    上面的代码表示:5/100*1,返回0.05,只需要将第三个参数设置为1即可


    展开全文
  • 离散 模运算

    千次阅读 2019-08-31 20:05:58
    模n加法 两数进行普通加法后,对和进行取余,模n乘法 两数进行普通乘法后,对积进行取余,, ▫ > ▫是模n加法 G={0,1,2,3,4,...,n-1} 模加法有幺元:0,并且每个元素都有逆元;, * > *是模n乘法 G={1,2,3,4,...,n-1}...
  • 两个位数很大,位数可能达到1e3甚至更高的数加法运算直接存储无法存储,常规使用字符串或者数组来存储时间复杂度是O(max(M,N)),但是空间复杂度是2(M+N)。M和N分别是两个数的位数大小 算法基本策略 模拟两个数进行加法...
  • 模运算

    2010-06-21 13:24:00
    p运算 给定一个正整数p,任意一个整数n,一定存在等式 <br /> n = kp + r <br />其中k、r是整数,且 0 ≤ r ,称呼k为n除以p的商,r为n除以p的余数。 <br />对于正整数p和整数a,b,...
  • 模运算性质

    2018-03-27 12:03:50
    给定一个正整数p,任意一个整数n,一定存在等式 :n = kp + r ;其中 k、r 是整数,且 0 ≤ r &...p加法: ,其结果是a+b算术和除以p的余数。p减法: ,其结果是a-b算术差除以p的余数。p乘...
  • 1、BigInteger的运算 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { // String num1 = "999999999999999999999999999999"; // ...
  • 模运算的基本性质

    2017-03-11 16:58:00
    基本理论  基本概念 给定一个正整数p,任意一个整数n,一定存在等式n=kp+r;  其中k、r是整数,且0≤r<p,称呼k为n除以p的商,r为n除以p的余数。...p加法:(a+b)%p,其结果是a+b算术和除以...
  • 模运算及其应用

    2010-07-19 22:13:00
    <br />一 基本理论: 基本概念: 给定一个正整数p,任意一个整数n,一定存在等式 n = kp + r ... p加法:(a + b) % p ,其结果是a+b算术和除以p的余数,也就是说,(a+b) = kp +r,则(a + b) %
  • 同余与模运算

    千次阅读 2015-08-08 17:00:42
    加法:(a+b) mod n = ((a mod n)+(b mod n))mod n 减法:(a-b) mod n = ((a mod n)-(b mod n)+n) mod n 乘法:ab mod n = (a mod n)(b mod n) mod n  2、大整数取模: char st[1000]; int m;
  • 以字符串读入,然后分解数位到数组中,然后模拟加法/乘法过程,逐个数位运算加法和乘法的思路是类似的。 注意点(模拟加法): (1)注意要根据长度判断(可以给位数少的大数增加前导0,使得长度相等)。同时...
  • 目录1 概述2 加法运算3 减法运算4 乘法运算5 C++实现 1 概述   由m×nm \times nm×n个数aija_{ij}aij​排成的mmm行nnn列的数表称为mmm行nnn列的矩阵,简称m×nm \times nm×n矩阵。记作: A=[a11a12⋯a1na21a22⋯...
  • 232加2^{32}加232加,计为+++:意思是普通加法的结果再进行232加2^{32}加232加计算。 如24加2^4加24加. 若,a = 14,b=15,(+)表示24加2^4加24加 则,a(+)b=(a+b)  mod  24=(14+15)mod16=...
  • FLOPS, floating point operations per second....上面的运算n次浮点乘法,n-1次浮点加法,所以总共FLOPS为2*n-1 先乘后加的浮点操作有n次,所以MACC为n 1.应用模型说明 首先明确模型的计算量一般是衡
  • 输出代码加法运算思路代码N进制计算减法运算思路代码乘法运算高精度数组×\times×单精度数字思路代码高精度数组×\times×高精度数组思路代码除法运算高精度除以单精度思路代码高精度除以高精度思路代码 ...
  • 高精度运算模版C语言

    2015-03-13 19:15:30
    #include #include #include #include #define maxx 100 ...//高精度加法: void add(char *s1,char *s2) { int n,m,i,j,a[maxx+10]={0},b[maxx+10]={0}; int l1=strlen(s1); int l2=strlen(s2); fo
  • 高精度四则运算模板

    千次阅读 2014-09-27 15:12:35
    大数模版 /*大数加法*/ # include # include # include void add(char* a,char* b,char* c) { int i,j,k,max,min,n,temp; char *s,*pmax,*pmin; max=strlen(a); min=strlen(b); if (max) {
  • 高精度运算模板C语言

    千次阅读 2013-02-26 14:38:25
    #include #include #include #include #define maxx 100 ...//高精度加法: void add(char *s1,char *s2) { int n,m,i,j,a[maxx+10]={0},b[maxx+10]={0}; int l1=strlen(s1); int l2=strlen(s2); fo
  • /*大数加法*/ # include<stdio.h> # include<string.h> # include<malloc.h> void add(char* a,char* b,char* c) { int i,j,k,max,min,n,temp; char *s,*pmax,*pmin; max=st...
  • 在DNA自装配加法的基础上,设计了一般的DNA自装配并行减法模型,算法的时间复杂度为[O(1)],空间复杂度为[O(n)],并通过实例验证了算法的有效性。算法的主要优点在于编码简单、效率高,且具有通用性。
  • 运算处理2的n次方的除法

    千次阅读 2019-11-11 11:58:06
    乘法、模运算、比较运算、循环语句和条件语句。 可以使用右移、加法以及按位运算。 #include<iostream> using namespace std; void div32(int n) { int x=(n>>31)&0x1F; //偏置常数 ...
  • 1.累加法化简 g(n)g(n)g(n): 在看看g(n)的定义 g(n) = f(1)^2 + f(2)^2 + … + f(n)^2; 因为 所以: 多写几个就可以看出累加法: 所以: 2.矩阵快速幂求 f(n)f(n)f(n): 由 [f(1),f(0)]×An=[f(n+1),f(n)] [f...
  • 自己从大数加法改过来的模板,低速计算n的t次幂,n,t小于等于100速度能够保证 模板 #include <bits/stdc++.h> using namespace std; string cal(string a,int cs) { string jk=a; string jc=a; reverse(a....
  • 比较简短的高精度加法和减法运算模板。大除法的日后更新。 1 /* 两个非负的大整数相加 */ 2 void big_plus(char a[],char b[],char ans[]) 3 { 4 int c[N],d[N]; 5 memset(c,0,sizeof(c)); memset(d,0,...
  • RSA大数运算实现(1024位n) (1)

    千次阅读 2018-12-08 21:20:33
    RSA大数运算(1024位)综述数据结构和宏数据结构及宏bignum.h中的函数定义bignum.h中函数声明函数实现方法加法减法乘法乘法算法除法取模数论中的一些函数求最大公因子和求逆运算费马素性检测中国剩余定理实现的...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 196
精华内容 78
关键字:

模n加法运算