$$\u6211\u4eec\u6709\u4e00\u4e2a\u8d28\u6570p$$
\n$$\\forall i\\in Z,def\\ q_{i}=[\\frac{p}{i}],r_{i}=p\\%i\\ st:\\ p = iq_{i}+r_{i} \\ (1)$$
\n$$def\\ i^{-1}*i\u22611\\ (mod\\ p)$$
\n$$(1)*i^{-1}$$
\n$$=>p*i^{-1}\u2261q_{i}+r_{i}*i^{-1}\\ (mod\\ p)$$
\n$$\u2235(p*i^{-1})\\%p\u22610\\ (mod\\ p)$$
\n$$\u2234r_{i}*i^{-1}\u2261-q_{i}\\ (mod\\ p)$$
\n$$i^{-1}\u2261-q_{i}*r_{i}^{-1}\\ (mod\\ p)$$
\n$$i^{-1}\u2261(p-[\\frac{p}{i}])*(p\\%i)^{-1}\\ (mod\\ p)$$
\n\u4ee3\u7801\u975e\u5e38\u7b80\u77ed\uff1a<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\nint MOD;\r\nint inv[1000005],n;\r\nint main(){\r\n\tscanf(\"%d%d\",&n,&MOD);\r\n\tinv[1]=1;\r\n\tfor(int i=2;i<=n;++i){\r\n\t\tinv[i]=(MOD-(MOD\/i))*inv[MOD%i]%MOD;\r\n\t}\r\n\tfor(int i=1;i<=n;++i){\r\n\t\tprintf(\"%d \",inv[i]); \r\n\t}\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
$$\u6211\u4eec\u6709\u4e00\u4e2a\u8d28\u6570p$$ $$\\forall i\\in Z,def\\ q_{i}=[\\frac{p}{i}], … <\/p>\n