Tính N! mod M với N là số lớn

[noname00 (HK boy)]

Thế thì tính mảng factorial[10^6+3] chứ, cần gì tính lẻ tẻ từ 1 -> 9.

[noname00 (HK boy)]

Sao bạn vẫn nghĩ N! mod 1000003 = 0 với N > 9 thế nhỉ, 10! = 3628800 mod 1000003 = 628791, 1000003 là số nguyên tố nên mấy cái số bé tí 10! sao có thể mod 1000003 = 0 được :v Nhân đủ 1000003! mới mod 1000003 ra 0 được.

Từ 1->8 thì N! mod M = N!
Từ 9->10^18 thì N! mod M = 0

Đâu ra lý thuyết a < m < b thì b mod m bằng 0 thế :v 1 < 2 < 3 nhưng 3 mod 2 có bằng 0 đâu :v

[Hieu_Pham (Hiếu Phạm)]

hiện tại cách e đã chạy đc là tạo mảng có 10^6+3 phần tử, mình bỏ vào for tính rồi lưu vào mảng 1 lần, kiểu i=0 thì 0! lưu vào a[0], i=1 thì kq=a[0].i rồi lưu vào a[1]… tới 10^6+3 thì cứ mỗi phần tử trong mảng là 1 giai thừa tương ứng với i để khi mình nhập N thì nó tự lấy a[N] ra tính luôn

[Hieu_Pham (Hiếu Phạm)]

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
using namespace std;
const ll N=1e6+5;
ll a[N+5];
void tinh()
{
    for (ll i=2 ;i<N;i++)
    for(ll j=i;j<=N;j+=i)
    a[j]++ ;
	FOR(i,2,N-1)
    a[i]=max(a[i]*i,a[i-1]);
}
int main()
{
	tinh();
	int n,t;
	cin >> t;
	while(t--)
	{
		cin >> n;
		cout << a[n]+n << endl;
	}
}

mình không hiểu tại sao khi dùng for(){ for() } thì chương trình bị đơ và time limit trong khi chỉ sửa for() for() như trong hàm trên lại chạy bình thường, ai giải thích hộ với :((

[Duong_Act (Lão Hạc)]

Vòng for lặp 1 triệu lồng trong for 1 triệu.
Ngay phát đầu lặp 1000 tỷ lần.
Nó sẽ chạy 8 kiếp không xong nhé.

[Hieu_Pham (Hiếu Phạm)]

ý mình là ko hiểu chỗ tại sao khi ghi bằng nhau lại chạy được ??? 2 cái này có gì khác nhau ấy

[Duong_Act (Lão Hạc)]

Code chính xác nó như thế nào ?

[rogp10]

Code trên tính sai rành rành rồi viết lại thôi.

[Hieu_Pham (Hiếu Phạm)]

bài for đó tính đúng mà bạn, mà còn tính nhanh hơn so khi code bth nữa, mình học theo thằng bạn thi ICPC đấy, đúng là phải học theo mấy thằng cỡ đó mấy khá nỗi :v

[noname00 (HK boy)]

Thi ICPC ACM cũng có dăm bảy loại, code sai là sai chứ cần gì phải giải thích :v

Code bình thường thì đâu cần FOR() các kiểu làm gì :v code xấu thế học theo thì tồi đi chứ có tốt lên được đâu :v